C语言数据结构之图的遍历实例详解
输入一组顶点，建立无向图的邻接矩阵。输入一组顶点，建立有向图的邻接表。分别对无向图和有向图进行DFS（深度优先遍历）和BFS（广度优先遍历）。写出深度优先遍历的递归和非递归算法。根据建立的有向图，判断该图是否是有向无环图，若是，则输出其一种拓扑有序序列。
实现代码：
|
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct{
char data;
ArcNode *firstarc;
}AdjList[MAX];
typedef struct{
AdjList vertices;
int vexnum;
int arcnum;
}ALGraph;
typedef struct{
int *base;
int front,rear;
}CqQueue;
void InitQueue(CqQueue &Q)
{//初始化一个队列
Q.base=(int*)malloc(MAX*sizeof(int));
Q.front=Q.rear=0;
}
int QueueEmpty(CqQueue Q)
{//判断队列是否为空
if(Q.rear==Q.front)
return 1;
return 0;
}
void EnQueue(CqQueue &Q,int e)
{//入队操作
if((Q.rear+1)%MAX==Q.front)
return;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAX;
}
void DeQueue(CqQueue &Q,int &e)
{//出队操作
if(Q.rear==Q.front)
return;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAX;
}
int LocateVex(ALGraph G,char v)
{//查找顶点v在图G中的位置
for(int i=0;i<G.vexnum;i++)
if(G.vertices[i].data==v)
return i;
return -1;
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==v)
return i;
return -1;
}
void CreateAdjList(ALGraph &G)
{//建立无向图的邻接表
int v,i,j,k;
char v1,v2;
ArcNode *p,*s;
printf("输入无向图的顶点数和边数：\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
getchar();
printf("输入图的顶点信息：\n");
for(v=0;v<G.vexnum;v++){
scanf("%c",&G.vertices[v].data);getchar();
G.vertices[v].firstarc=NULL;
}
printf("输入无向图的边：\n");
for(k=0;k<G.vexnum;k++){
scanf("%c%c",&v1,&v2);
getchar();
i=LocateVex(G,v1);
j=LocateVex(G,v2);
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=j;
s->nextarc=NULL;
if(!G.vertices[i].firstarc)
G.vertices[i].firstarc=s;
else{
p=G.vertices[i].firstarc;
while(p->nextarc)
p=p->nextarc;
p->nextarc=s;
}
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=i;
s->nextarc=NULL;
if(!G.vertices[j].firstarc)
G.vertices[j].firstarc=s;
else{
p=G.vertices[j].firstarc;
while(p->nextarc)
p=p->nextarc;
p->nextarc=s;
}
}
}
int visited[MAX];
void DFS(ALGraph G,int v)
{//从顶点v开始对图G进行深度优先搜索
ArcNode *p;
printf("%3c",G.vertices[v].data);
visited[v]=1;
for(p=G.vertices[v].firstarc;p;p=p->nextarc)
if(!visited[p->adjvex])
DFS(G,p->adjvex);
}
void DFSTraverse(ALGraph G)
{//对用邻接表存储的无向图G进行深度优先遍历
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=0;
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v);
}
void BFSTraverse(ALGraph G)
{//对用邻接表存储的无向图G进行深度优先遍历
int u,v;
CqQueue Q;
ArcNode *p;
for(v=0;v<G.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=0;v<G.vexnum;v++)
if(!visited[v]){
printf("%3c",G.vertices[v].data);
visited[v]=1;
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(Q,u);
for(p=G.vertices[u].firstarc;p;p=p->nextarc)
if(!visited[p->adjvex]){
printf("%3c",G.vertices[p->adjvex].data);
visited[p->adjvex]=1;
EnQueue(Q,p->adjvex);
}
}
}
}
int main(){
ALGraph G;
printf("建立无向图的邻接表：\n");
CreateAdjList(G);
printf("无向图的深度优先遍历序列如下：\n");
DFSTraverse(G);
printf("\n\n无向图的广度优先遍历序列如下：\n");
BFSTraverse(G);
printf("\n");
return 0;
}
|
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/qq_26816591/article/details/49585175