数据结构实验七：图的遍历
图的遍历
1 实验目的
- 掌握图的逻辑结构；
- 掌握图的邻接矩阵、邻接表存储结构；
- 验证图的邻接矩阵、邻接表存储及其深度优先遍历、广度优先遍历操作的实现。
2 实验内容
- 建立教材P310页图8.54所示的有向图的邻接矩阵、邻接表并分别输出；
- 输出图8.54的有向图从顶点0开始的深度遍历序列；
- 对已经建立的有向图从顶点0开始的广度优先遍历序列。
3 软件程序
graph.cpp：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <malloc.h>
#include <stdio.h>
#define MAXV 100
#define INF 32767
typedef char InfoType;
/*------------------------------以下定义邻接矩阵类型------------------------------*/
typedef struct
{
int no;
InfoType info;
}VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n, e;
VertexType vexs[MAXV];
}MatGraph;
/*--------------------------------------------------------------------------------*/
/*-------------------------------以下定义邻接表类型-------------------------------*/
typedef struct ANode
{
int adjvex;
struct ANode* nextarc;
int weight;
}ArcNode;
typedef struct Vnode
{
InfoType info;
ArcNode* firstarc;
}VNode;
typedef struct
{
VNode adjlist[MAXV];
int n, e;
}AdjGraph;
/*--------------------------------------------------------------------------------*/
/*-----------------------------邻接矩阵的基本运算算法-----------------------------*/
void CreateMat(MatGraph& g, int A[MAXV][MAXV], int n, int e) //创建图的邻接矩阵
{
int i, j;
g.n = n; g.e = e;
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
g.edges[i][j] = A[i][j];
}
void DispMat(MatGraph g) //输出邻接矩阵g
{
int i, j;
for (i = 0; i < g.n; i++)
{
for (j = 0; j < g.n; j++)
if (g.edges[i][j] != INF)
printf("%4d", g.edges[i][j]);
else
printf("%4s", "∞");
printf("\n");
}
}
/*--------------------------------------------------------------------------------*/
/*------------------------------邻接表的基本运算算法------------------------------*/
void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表
{
int i,j;
ArcNode *p;
G=(AdjGraph *)malloc(sizeof(AdjGraph));
for (i=0;i<n;i++) //给邻接表中所有头结点的指针域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //检查邻接矩阵中每个元素
for (j=n-1;j>=0;j--)
if (A[i][j]!=0 && A[i][j]!=INF) //存在一条边
{
p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点p
p->adjvex=j;
p->weight=A[i][j];
p->nextarc=G->adjlist[i].firstarc; //采用头插法插入结点p
G->adjlist[i].firstarc=p;
}
G->n=n; G->e=n;
}
void DispAdj(AdjGraph* G) //输出邻接表G
{
int i;
ArcNode* p;
for (i = 0; i < G->n; i++)
{
p = G->adjlist[i].firstarc;
printf("%3d: ", i);
while (p != NULL)
{
printf("%3d[%d]→", p->adjvex, p->weight);
p = p->nextarc;
}
printf("∧\n");
}
}
void DestroyAdj(AdjGraph*& G) //销毁图的邻接表
{
int i;
ArcNode* pre, * p;
for (i = 0; i < G->n; i++) //扫描所有的单链表
{
pre = G->adjlist[i].firstarc; //p指向第i个单链表的首结点
if (pre != NULL)
{
p = pre->nextarc;
while (p != NULL) //释放第i个单链表的所有边结点
{
free(pre);
pre = p; p = p->nextarc;
}
free(pre);
}
}
free(G); //释放头结点数组
}
/*--------------------------------------------------------------------------------*/
sqqueue.cpp：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
#include<malloc.h>
#define MaxSize 1000
typedef char ElemType;
typedef struct Quene{ //定义顺序队
int front; //队头指针
char data[MaxSize]; //存放队中元素
int rear; //队尾指针
}SqQueue; //struct Queue 的别名
void InitQueue(SqQueue * &q)//初始化队列
{
q=(SqQueue *)malloc(sizeof(SqQueue)); //分配一个空间
q->front=q->rear=-1; //置 -1
}
void DestroyQueue(SqQueue * &q)//销毁队列
{
free(q); //释放内存
}
bool QueueEmpty(SqQueue * &q)//判断队列是否为空
{
if(q->front==q->rear){ //首指针和尾指针相等，说明为空
return true; //返回真
}
else{
return false; //返回假
}
}
bool enQueue(SqQueue * &q,int c)//进队
{
if(q->rear==MaxSize-1){ //判断队列是否满了
return false; //返回假
}
q->rear++; //头指针加 1
q->data[q->rear]=c; //传值
return true; //返回真
}
bool deQueue(SqQueue * &q,int &ch)//出队
{
if(q->front==q->rear){ //判断是否空了
return false; //返回假
}
q->front++; //尾指针加 1
ch=q->data[q->front]; //取值
return true; //返回真
}
main.cpp：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
/*将图的邻接矩阵、邻接表结构定义、建立以及各种遍历算法设计放到这里*/
#include "graph.cpp"
#include "sqqueue.cpp"
int visited[MAXV] = { 0 };
/*----------------------------------------------------------------*/
void DFS(AdjGraph* G, int v)
{
ArcNode* p;
visited[v] = 1;
printf("%d", v);
p = G->adjlist[v].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 0)
{
DFS(G, p->adjvex);
}
p = p->nextarc;
}
}
void BFS(AdjGraph* G, int v)
{
int w, i; ArcNode* p;
SqQueue* qu;
InitQueue(qu);
int visited[MAXV];
for (i = 0; i < G->n; i++) visited[i] = 0;
printf("%2d", v);
visited[v] = 1;
enQueue(qu, v);
while (!QueueEmpty(qu))
{
deQueue(qu, w);
p = G->adjlist[w].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 0)
{
printf("%2d", p->adjvex);
visited[p->adjvex] = 1;
enQueue(qu, p->adjvex);
}
p = p->nextarc;
}
}
printf("\n");
}
void DFS1(AdjGraph* G, int v) //非递归深度优先遍历算法
{
ArcNode* p;
int St[MAXV];
int top = -1, w, x, i;
for (i = 0; i < G->n; i++)
visited[i] = 0; //顶点访问标志均置成0
printf("%3d", v); //访问顶点v
visited[v] = 1; //置顶点v已访问
top++; St[top] = v; //将顶点v进栈
while (top > -1) //栈不空循环
{
x = St[top]; //取栈顶顶点x作为当前顶点
p = G->adjlist[x].firstarc; //找顶点x的第一个相邻点
while (p != NULL)
{
w = p->adjvex; //x的相邻点为w
if (visited[w] == 0) //若顶点w没有访问
{
printf("%3d", w); //访问顶点w
visited[w] = 1; //置顶点w已访问
top++; //将顶点w进栈
St[top] = w;
break; //退出循环，即再处理栈顶的顶点(体现后进先出)
}
p = p->nextarc; //找顶点x的下一个相邻点
}
if (p == NULL) top--; //若顶点x再没有相邻点，将其退栈
}
printf("\n");
}
int main()
{
MatGraph g;
AdjGraph* G;
int A[MAXV][MAXV] = {
{0,5,INF,7,INF,INF},
{INF,0,4,INF,INF,INF},
{8,INF,0,INF,INF,9},
{INF,INF,5,0,INF,6},
{INF,INF,INF,5,0,INF},
{3,INF,INF,INF,1,0} };
int n = 6, e = 10; //顶点数、边数
CreateMat(g, A, n, e);
printf("(1)图G的邻接矩阵:\n"); DispMat(g);
CreateAdj(G, A, n, e);
printf("图G的邻接表:\n"); DispAdj(G);
printf("从顶点0开始的DFS(递归算法):\n");
DFS(G, 0); printf("\n");
printf("从顶点0开始的DFS(非递归算法):\n");
DFS1(G, 0);
printf("从顶点0开始的BFS:\n");
BFS(G, 0);
DestroyAdj(G);
return 1;
}
4 实验结果
本文由作者按照 CC BY 4.0 进行授权