-
名：
业：
图的基本操作与实现的课程设
告
中国矿业大学徐海学院计算机系
《软件认知实践》报告
_
学号：
___________________
计报
姓
专
_______________
____________________________
年
12
月
日
设计题目：
指导教师：
2013
30
第
1
章题目概述
第
1.1
节题目要求
< br>.
第
1.2
节主要难点
第
2
章系
统流程
第
3
章数据结构和算法
第
4
章核心代码分析
..
第
5
章复杂度分析
参考文献
第一章题目概述
G
；
.2
.2
.3
.4
.5
第
1.1
节题目要求
.6
(1)
自选存储结构，输入含
n
个顶点
(
用字符表
示顶点
)
和
e
条边的图
25
25
(2)
求每个顶点的度，输出结果；
(3)
指定任意顶点
x
为初始顶点，对图
G
作
DFS
遍历，输出
DFS
< br>顶点序列
(
提示
:
使用一个栈
实
现
DFS);
⑷指定任意顶点
x
为初始顶点，对图
G
作
BFS
遍历，输出
BFS
顶点序列
(
提示
:
使用一个队列
实现
BFS);
(5)
输入顶点
x,
查找图
G:
若存在含
x
的顶点，则删除该结点及与之相关连的边，并作
DFS
遍
历
(
执行操作
3)
；
< br>否则输出信息“无
x”
(6)
判断图
G
是否是连通图，输出信息
“YES” /
“NO”；
(7)
如果选用的存储结构是邻接矩阵
,
则用邻接矩阵的信息
生成图
G
的邻接表，即复制图
G, <
/p>
然再执行操作
(2);
反之亦然。
第
1.
2
节主要难点
(1)
自选存储结构创建一个图：通
过用户从键盘敲入的两个数值分别确定图的顶点数和边
数，选
择邻接矩阵存储结构将图的结点信息存储在一个顺序表中，图的边信息存储在一个二维
数组中。
(2)
求每个顶点的度
:
1.
邻接
矩阵存储结构下求每个顶点的度：利用图的邻接矩阵，每个顶点所在行和所在列的
边的权值如果存在则该顶点的度
+1,
依次
算出每个顶点的度，并且记录在一个数组中输出。
2.
邻接表存储结构下求每个顶点的
度：定义一个邻接边指针循环指向顶点的邻接边单链表
头结点
，当结点不空时，该顶点的出度
+1,
邻接边弧头结点的入度<
/p>
+1,
依次求出每个顶点的出度
和入度之和就为该顶点的度。
(3)
图的深度优先遍历：采取邻接
矩阵结构，指定任意顶点
x
为初始顶点
1.
访问结点
V
并标记结点
V
己访问；
2.
查找结点
v
的第一个邻接结点
w
；
3.
若结点
v
的邻接结点
w
存在，则继续执行，否则算法结束；
4.
若结点
w
尚未被访问，则递归访问结点
w
；<
/p>
5.
查找结
点
v
的
w
邻接
结点的下一个邻接结点
w,
转到步骤
3
o
(4)
图的广度优先遍历：采取
邻接矩阵结构，指定任意顶点
x
为初始顶点，利用顺序循环队<
/p>
列以保持访问过的结点的顺序
1.
首先访问初始结点
v
并标记结点
v
为已访问；
2.
结点
v
入队列；
3.
当队列非空时则继续执行，否则算法结束；
4.
出队列取得队头结点
u
；
5.
查找
u
的第一个邻接结点
w
；
6.
若
< br>u
的邻接结点
w
不存在则转到步
骤
3,
否则循环执行下列步骤：
6.1
若结点
w
尚
未被访问，则访问结点
w
并标记结点
w
为已访问；
6.
2
结点
w
入队列；
6. 3
查找结点
u
< br>的
w
邻接结点的下一个邻接结点
w,
转到步骤
6 o
(5)
判断有向图的强连通性：采取
邻接表结构，在图中寻找一个包含所有顶点且首尾相连的
环，若这样的环存在，则该图为强连通图，否则不为强连通图。
(6)
用邻接矩阵的信息生成邻接表
：定义一个邻接表的边信息结构体，将邻接矩阵的边信息
转换成邻接表的边信息存储到邻接边的单链表中。
第二章系统流程图
第三章数据结构和算法
(1)
有向图顶点的数据类型
DataType
定义如下：
typedef int DataType
；
(2)
邻接矩阵存储结构下图的结构体定义如下：
typedef struct
{
SeqList Vertices
；
int edge[MaxVertices][MaxVertices]
；
int
numOfEdges
；
}AdjMGraph
；
(3)
邻接矩阵存储结构下图的边信息结构体定义如下：
typedef struct
{
int row
；
int col
；
int weight
；
}RowColWeight
；
(4)
邻接表存储结构下图的结构体定义如下：
typedef struct Node
{
int dest
；
struct Node
*next
；
}Edge
；
typedef struct
{
DataType data
；
int sorce
；
Edge *adj
；
}AdjLHeight
；
typedef struct
{
AdjLHeight
a[MaxVertices]
；
int
numOfVerts
；
int
numOfEdges
；
}AdjLGraph
；
(5)
邻接表存储结构下图的边信息结构体定义如下：
typedef struct
{
int row
；
int col
；
}RowCol
；
(6)
顺序循环队列的结构体定义如下：
typedef struct
{
DataType
queue[MaxQueueSize]
；
int rear
；
int front
；
int count
；
}SeqCQueue
；
(7)
顺序表的结构体定义如下：
typedef struct
{
DataType list
[MaxSize]
；
int
size
；
JSeqList
；
第四章核心代码分析
源程序存放在八
个文件夹中，文件
SeqList.h
是顺序表的结构体定义和
操作函数，文件
SeqCQueue.
h
是顺序循环队列的结构体定义和操作函数，文件
AdjM
Graph.
h
是邻接矩阵存储结构
下图的结构体定义和操作函数，文件
AdjMGraphCre
ate.
h
是邻接矩阵存储结构下图的创建函数
,
文件
AdjLGraph. h
是邻接表存储结构下图的结构体定义和操作函数，文件
AdjLGraphCr
eate. h
是
邻接表存储结构下图的创建函数，文件
AdjMGraphTraverse.
h
是邻接矩阵存储结构下图的深
度优
先遍历和广度优先遍历操作函数，文件图的基本操作与实现
.<
/p>
c
是主函数。
(1)
/*
文件
SeqList. h
*/
typedef struct
DataType
list [MaxSize]: int size;
JSeqList;
void Listinitiate(SeqList *L)
L->size=0;
}
int
ListLength(SeqList L)
{
return L. size;
)
int Listinsert (SeqList *L, int i,
DataType x)
{
int j;
if(L->size>=MaxSize)
{
printfC
数组已满无法插入！
n
return 0;
)
else if(i<0||i>L->size)
(
printf
(”参数不合法
！
n
return 0;
)
else
(
for (j=L->size;j>i;i
—
)L->list[j]=L->list[j-1];
L->list[i]=x;
L->size++;
retxirn 1;
)
}
int ListDelete(SeqList *L)int i,
DataType *x)
{
int
j
；
if(L->size<=0)
(
printf
r
顺序表己空无数据元素可删！
n
return 0;
)
else if(i<0||i>L->size-l)
printf
(
参数
i
不合法
!
rT);
return 0;
}
else
{
*x=L->list[i];
for(j=i+l;j<=L->size~l;j++)L->list[j-l]=L->list[j]
;
L->size
—
;
return 1;
)
}
int ListGet(SeqList L, int i, DataType
*x)
{
if (i<0||i>L. size-1)
{
printfC
参数
i
不合法！
n
return 0;
)
else
(
*x=L.
list[i];
return 1;
}
}
(2)
/
*
文件
SeqCQueue. h */
typedef struct
{
DataType
queue[MaxQueueSize];
int rear;
int front;
int count;
}SeqCQueue;
void
Queueinitiate(SeqCQueue *Q)
{
Q->rear=0;
Q-
〉
front =0;
Q->count =0;
}
int QueueNotEmpty(SeqCQueue Q)
{
if(Q. count 1=0) return 1;
else return 0;
}
int QueueAppend(SeqCQueue *Q, DataType
x)
{
if(Q->count>0&&Q->rear==Q->front)
{
printfC
队列已满无法插入
!”)；
return 0;
)
else
(
Q->queue
[Q->rear]=x;
Q->rear =(Q->rear
+1)%MaxQueueSize;
Q->count ++;
return 1;
}
)
int QueueDelete(SeqCQueue *Q, DataType
*d)
{
if(Q->count ==0)
(
printfC
队列己空无数据出
队列
!
n
；
)
else
(
*d=Q->queue[Q->front];
Q->front=(Q->front+l)%MaxQueueSize;
Q->count
—
;
return 1;
}
)
return 0;
int QueueGet(SeqCQueue Q,
DataType*d)
{
if (Q. count
==0)
{
printfC
队列已
空无数据出队列
!
n
return
0;
}
else
*d=Q.
queue [Q. front ]; return 1;
}
(3)
/*
文件
AdjMGraph. h*/
#include*SeqList. h” typedef struct
{
SeqList Vertices;
〃存放结点的顺序表
int
edge [MaxVertices] [MaxVertices];
〃存放边的邻接矩阵
int
numOfEdges;
〃边的条数
} AdjMGraph;
〃边的结构体定义
void
Initiate (AdjMGraph *G, int n)
//
初始化
{ int i, j;
for(i=0;i
for(j=0;j
(
if(i=j)
G->edge[i][j]=0;
else
G->edge[i] [j]=MaxWeight;
}
G->numOfEdges=O;
〃边的条数置为
0
Listinitiate (&G->Vertices);
//
顺序表初始化
}
void
InsertVertex(AdjMGraph *G, DataType vertex)
〃在图
G
中插入结点
vertex {
Listinsert (&G->Vertices, G->Vertices.
size, vertex);
〃顺序表尾插入
}
void InsertEdge(AdjMGraph
*G, int vl, int v2, int weight)
//
在图
G
中插入边
v2>,
边
的权为
weight {
if(vl<01|vl>G->Vertices. size
v2<01|v2>G->Vertices. size)
printf ('
参数
vl
或
v2<
/p>
越界出错
!
n
}
G->edge[vl][v2]=weight;
G->numOfEdges++;
}
void De let eEdge (AdjMGraph *G, int
vl, int v2)
//
在图中删除边
{
if(vl<01|vl>G->Vertices. size
v2<01|v2>G->Vertices. size| i vl==v2)
{
printf (*
参数
vl
或
v2
越界出借
!
n
exit(l);
)
if(G->edge[vl][v2]==MaxWeight||vl==v2)
{
printf
C
该边不存在
!
n
exit (0);
)
G->edge[vl][v2]=MaxWeight;
G->numOfEdges
一；
}
void
DeleteVerten(AdjMGraph *G, int v)
//
删除结点
v
{
int
n=ListLength(G->Vertices), i> j;
DataType x;
for(i=0;i
〃计算删除后的边数
(
for (j=0;j
if ((i=v|
| j=v)&&G->edge[i] [j]>O&&G->edge[i]
[j]
G->num0f
Edges
—
;
//
计算被删除边
}
for(i=v;i
//
删除第
v
行
(
for(j=0;j
G->edge[i][j]=G->edge[i+l] [j];
)
for(i=0;i
〃删除第
v
列
(
-
-
-
-
-
-
-
-
-
上一篇：实现图的遍历算法实验报告
下一篇：数据结构C语言版 求关节点