广度优先搜索遍历(无向图)

本文主要是介绍广度优先搜索遍历(无向图)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

全局变量

int visited[MAXVEX] = { 0 };/*访问标志数组*/

BFSTraverse函数

 1 /***************************************************
 2 * Name: BFSTraverse
 3 * Called By: main
 4 * Parameter: G 邻接表
 5 * Description: 遍历图G的所有连通子图
 6 ****************************************************/
 7 void BFSTraverse(ALGraph* G)
 8 {
 9     int i = 1;
10     for (i = 1; i <= G->vexnum; i++)
11     {
12         if (visited[i] == 0)
13         {
14             BFS(G, i);
15         }
16     }
17 }

BFS函数

 1 /******************************************************
 2 * Name: BFS
 3 * Call: InitQueue, InLQueue, OutLQueue, FristAdjvex,
 4 *          NextAdjvex
 5 * Called By: BFSTraverse
 6 * Parameter: G 邻接表, v0 初始顶点
 7 * Description: 遍历图G中一个以顶点v0开始的连通子图
 8 *******************************************************/
 9 void BFS(ALGraph* G, int v0)
10 {
11     int v = 0;/*保存在队列中的顶点信息*/
12     int adjvex = 0;/*邻接顶点*/
13     LQueue* Q = (LQueue*)calloc(1, sizeof(LQueue));/*队列指针*/
14     ArcNode* P = NULL;
15 
16     printf("%c", G->vex[v0].vexdata);
17     visited[v0] = 1;
18     InitLQueue(Q);
19     InLQueue(Q, v0);
20     /*当队列非空*/
21     while (Q->front != Q->rear)
22     {
23         OutLQueue(Q, &v);
24         adjvex = FristAdjvex(G, v);
25         /*当邻接顶点adjvex存在，即不为0*/
26         while (adjvex)
27         {
28             /*当邻接顶点adjvex未访问过*/
29             if (visited[adjvex] == 0)
30             {
31                 printf("%c", G->vex[adjvex].vexdata);
32                 visited[adjvex] = 1;
33                 InLQueue(Q, adjvex);
34             }
35             adjvex = NextAdjvex(G, v, adjvex);
36         }
37     }
38 }

FristAdjvex函数

 1 /***************************************************
 2 * Name: FristAdjvex
 3 * Called By: BFS
 4 * Parameter: G 邻接表, v0 顶点
 5 * return: 若vex顶点的首个邻接顶点存在，则返回这
 6 *              个邻接顶点在顶点表中的下标；否则返回0
 7 ****************************************************/
 8 int FristAdjvex(ALGraph* G, int v0)
 9 {
10     if (G->vex[v0].head)
11     {
12         return G->vex[v0].head->adjvex;
13     }
14     return 0;
15 }

NextAdjvex函数

 1 /***************************************************
 2 * Name: NextAdjvex
 3 * Called By: BFS
 4 * Parameter: G 邻接表, v0 顶点, adjvex 邻接顶点
 5 * return: 查找与顶点vex邻接的adjvex顶点的下一个与
 6 *              顶点vex邻接的顶点，返回其在顶点表中的位
 7 *              置下标，若下一邻接顶点不存在，则返回0
 8 ****************************************************/
 9 int NextAdjvex(ALGraph* G, int v0, int adjvex)
10 {
11     ArcNode* P = G->vex[v0].head;
12     /*定位到顶点v0的邻接顶点adjvex*/
13     while (P && P->adjvex != adjvex)
14     {
15         P = P->next;
16     }
17     /*当v0的下一邻接顶点存在时*/
18     if (P && P->next)
19     {
20         return P->next->adjvex;
21     }
22     return 0;
23 }

源代码

  1 /************************************************************
  2 * Name: 广度优先搜索遍历(无向图)
  3 * Date: 2022.01.23
  4 * Author: 吕辉
  5 * Description:    广度优先搜索(Breadth Frist Search)类似树的
  6 *                        按层次遍历；代码采用邻接表来存储无向图、
  7 *                        使用链式队列来保存顶点、通过全局变量visited
  8 *                        数组来标记顶点是否已被遍历
  9 *************************************************************/
 10 #define _CRT_SECURE_NO_WARNINGS
 11 #include <stdio.h>
 12 #include <stdlib.h>
 13 
 14 #define MAXVEX 20
 15 /*邻接表的抽象数据结构*/
 16 typedef struct ArcNode
 17 {
 18     int adjvex;
 19     struct ArcNode* next;
 20 }ArcNode;/*边表*/
 21 
 22 typedef struct VexNode
 23 {
 24     char vexdata;
 25     ArcNode* head;
 26 }VexNode;/*顶点表*/
 27 
 28 typedef struct
 29 {
 30     int vexnum;/*顶点数*/
 31     int arcnum;/*弧数*/
 32     VexNode vex[MAXVEX];
 33 }ALGraph;/*邻接表*/
 34 
 35 /*链队列的抽象数据结构*/
 36 typedef struct QNode
 37 {
 38     int data;
 39     struct QNode* next;
 40 }QNode;/*队列结点*/
 41 
 42 typedef struct
 43 {
 44     QNode* front;
 45     QNode* rear;
 46 }LQueue;/*链队列*/
 47 
 48 int visited[MAXVEX] = { 0 };/*访问标志数组*/
 49 
 50 /*队列相关函数*/
 51 void InitLQueue(LQueue* Q);
 52 void InLQueue(LQueue* Q, int data);
 53 void OutLQueue(LQueue* Q, int* data);
 54 /*邻接表相关函数*/
 55 void CreateGraph(ALGraph* G);
 56 int LocateVex(ALGraph* G, char vex);
 57 /*深度优先遍历相关函数*/
 58 void BFS(ALGraph* G, int v0);
 59 int FristAdjvex(ALGraph* G, int v0);
 60 int NextAdjvex(ALGraph* G, int v0, int adjvex);
 61 void BFSTraverse(ALGraph* G);
 62 
 63 int main(void)
 64 {
 65     ALGraph G;
 66     CreateGraph(&G);
 67     BFSTraverse(&G);
 68     system("pause");
 69     return 0;
 70 }
 71 /***************************************************
 72 * Name: InitLQueue
 73 * Called By: BFS
 74 * Parameter: Q 链队列
 75 * Description: 初始化队列
 76 ****************************************************/
 77 void InitLQueue(LQueue* Q)
 78 {
 79     QNode* P = (QNode*)calloc(1, sizeof(QNode));
 80     Q->front = P;
 81     Q->rear = P;
 82     P = NULL;
 83     free(P);
 84 }
 85 /***************************************************
 86 * Name: InLQueue
 87 * Called By: BFS
 88 * Parameter: Q 链队列, data 入队元素    
 89 * Description: 把元素data入队
 90 ****************************************************/
 91 void InLQueue(LQueue* Q, int data)
 92 {
 93     QNode* P = (QNode*)calloc(1, sizeof(QNode));
 94     P->data = data;
 95     Q->rear->next = P;
 96     Q->rear = P;
 97 }
 98 /***************************************************
 99 * Name: OutLQueue
100 * Called By: BFS
101 * Parameter: Q 链队列, data 出队元素
102 * Description: 出队首元素，并保存在data引用地址中
103 ****************************************************/
104 void OutLQueue(LQueue* Q, int* data)
105 {
106     QNode* P = NULL;
107     if (Q->front == Q->rear)
108     {
109         printf("\n出队失败，空队列\n");
110         exit(-1);
111     }
112     else
113     {
114         P = Q->front->next;
115         Q->front->next = P->next;
116         (*data) = P->data;
117         free(P);
118         /*链队列仅有一个元素结点时，删除后还需要修改尾指针*/
119         if (Q->front->next == NULL)
120         {
121             Q->rear = Q->front;
122         }
123     }
124 }
125 /***************************************************
126 * Name: CreateGraph
127 * Call: LocateVex
128 * Called By: main
129 * Parameter: G 邻接表
130 * Description: 创建邻接表
131 ****************************************************/
132 void CreateGraph(ALGraph* G)
133 {
134     int i = 1;
135     int j = 1;
136     int k = 1;
137     char vex1 = '\0';
138     char vex2 = '\0';
139     ArcNode* P = NULL;
140     ArcNode* Pre = NULL;
141 
142     printf("请输入顶点数和弧数(逗号分隔)：");
143     scanf("%d%*c%d", &G->vexnum, &G->arcnum);
144     for (i = 1; i <= G->vexnum; i++)
145     {
146         printf("请输入第%d个顶点：", i);
147         scanf(" %c", &G->vex[i].vexdata);
148         G->vex[i].head = NULL;
149     }
150     for (k = 1; k <= G->arcnum; k++)
151     {
152         printf("请输入第%d条弧的两端点(逗号分隔)：", k);
153         scanf(" %c%*c%c", &vex1, &vex2);
154         i = LocateVex(G, vex1);
155         j = LocateVex(G, vex2);
156         /*把弧信息链接到其中一端的顶点表中*/
157         P = (ArcNode*)calloc(1, sizeof(ArcNode));
158         P->adjvex = j;
159         if (G->vex[i].head == NULL)
160         {
161             G->vex[i].head = P;
162         }
163         else
164         {
165             Pre = G->vex[i].head;
166             while (Pre->next)
167             {
168                 Pre = Pre->next;
169             }
170             Pre->next = P;
171             /*把弧信息链接到另一端的顶点表*/
172             P = (ArcNode*)calloc(1, sizeof(ArcNode));
173             P->adjvex = i;
174             if (G->vex[j].head == NULL)
175             {
176                 G->vex[j].head = P;
177             }
178             else
179             {
180                 Pre = G->vex[j].head;
181                 while (Pre->next)
182                 {
183                     Pre = Pre->next;
184                 }
185                 Pre->next = P;
186             }
187         }
188     }/*for循环*/
189     P = NULL;
190     free(P);
191 }
192 /***************************************************
193 * Name: LocateVex
194 * Called By: Create
195 * Parameter: G 邻接表, vex 顶点
196 * return :    若顶点表中存在该顶点则返回其在顶点表中
197 *                的位置下标；否则返回0
198 ****************************************************/
199 int LocateVex(ALGraph* G, char vex)
200 {
201     int i = 1;
202     for (i = 1; i <= G->vexnum; i++)
203     {
204         if (G->vex[i].vexdata == vex)
205         {
206             return i;
207         }
208     }
209     return 0;
210 }
211 /******************************************************
212 * Name: BFS
213 * Call: InitQueue, InLQueue, OutLQueue, FristAdjvex,
214 *          NextAdjvex
215 * Called By: BFSTraverse
216 * Parameter: G 邻接表, v0 初始顶点
217 * Description: 遍历图G中一个以顶点v0开始的连通子图
218 *******************************************************/
219 void BFS(ALGraph* G, int v0)
220 {
221     int v = 0;/*保存在队列中的顶点信息*/
222     int adjvex = 0;/*邻接顶点*/
223     LQueue* Q = (LQueue*)calloc(1, sizeof(LQueue));/*队列指针*/
224     ArcNode* P = NULL;
225 
226     printf("%c", G->vex[v0].vexdata);
227     visited[v0] = 1;
228     InitLQueue(Q);
229     InLQueue(Q, v0);
230     /*当队列非空*/
231     while (Q->front != Q->rear)
232     {
233         OutLQueue(Q, &v);
234         adjvex = FristAdjvex(G, v);
235         /*当邻接顶点adjvex存在，即不为0*/
236         while (adjvex)
237         {
238             /*当邻接顶点adjvex未访问过*/
239             if (visited[adjvex] == 0)
240             {
241                 printf("%c", G->vex[adjvex].vexdata);
242                 visited[adjvex] = 1;
243                 InLQueue(Q, adjvex);
244             }
245             adjvex = NextAdjvex(G, v, adjvex);
246         }
247     }
248 }
249 /***************************************************
250 * Name: FristAdjvex
251 * Called By: BFS
252 * Parameter: G 邻接表, v0 顶点
253 * return: 若vex顶点的首个邻接顶点存在，则返回这
254 *              个邻接顶点在顶点表中的下标；否则返回0
255 ****************************************************/
256 int FristAdjvex(ALGraph* G, int v0)
257 {
258     if (G->vex[v0].head)
259     {
260         return G->vex[v0].head->adjvex;
261     }
262     return 0;
263 }
264 /***************************************************
265 * Name: NextAdjvex
266 * Called By: BFS
267 * Parameter: G 邻接表, v0 顶点, adjvex 邻接顶点
268 * return: 查找与顶点vex邻接的adjvex顶点的下一个与
269 *              顶点vex邻接的顶点，返回其在顶点表中的位
270 *              置下标，若下一邻接顶点不存在，则返回0
271 ****************************************************/
272 int NextAdjvex(ALGraph* G, int v0, int adjvex)
273 {
274     ArcNode* P = G->vex[v0].head;
275     /*定位到顶点v0的邻接顶点adjvex*/
276     while (P && P->adjvex != adjvex)
277     {
278         P = P->next;
279     }
280     /*当v0的下一邻接顶点存在时*/
281     if (P && P->next)
282     {
283         return P->next->adjvex;
284     }
285     return 0;
286 }
287 /***************************************************
288 * Name: BFSTraverse
289 * Called By: main
290 * Parameter: G 邻接表
291 * Description: 遍历图G的所有连通子图
292 ****************************************************/
293 void BFSTraverse(ALGraph* G)
294 {
295     int i = 1;
296     for (i = 1; i <= G->vexnum; i++)
297     {
298         if (visited[i] == 0)
299         {
300             BFS(G, i);
301         }
302     }
303 }

这篇关于广度优先搜索遍历(无向图)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！