图的广度优先搜索（邻接表）

winston

图的遍历(Traversing Graph)是指从图中某一顶点出发访问图中其余顶点，且使每个顶点仅被访问一次。

广度优先搜索(Breadth First Search)

       广度优先搜索假设从图中某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再分别从这些邻接点出发依次访问它们的邻接点，并使先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问（因此需要用队列来存储顶点），直到图中所有已被访问的顶点的邻接点都被访问为止。如果此时图中还有未被访问的顶点，则另选图中未被访问的顶点作为起点，重复上述过程，直到图中所有顶点都被访问为止。

采用邻接表存储图的具体实现如下：#include <iostream>

2. #include <queue>
3. #include <cstdio>
4. #include <cstdlib>
5. using namespace std;
7. #define VERTEXNUM 100 //顶点个数
8. typedef char VertexType;
9. typedef int EdgeType;
10. typedef enum{FALSE, TRUE} Boolean;
11. Boolean visited[VERTEXNUM];
13. /***************************************
14. *
15. * 邻接表存储结构
16. *
17. * *************************************/
18. typedef struct node
19. {
20.         int adjvex; //顶点位置
21.         struct node *next; //指向下一条边的指针
22. }EdgeNode;
24. typedef struct vnode
25. {
26.         VertexType vertex; //顶点信息
27.         EdgeNode *firstedge; //指向第一条依附该顶点的边的指针
28. }AdjList[VERTEXNUM];
30. typedef struct
31. {
32.         AdjList vertexs; //邻接表
33.         int vernum, edgenum; //图中当前的顶点和边数
34. }Graph;
36. /***************************************
37. *
38. * 建立图的邻接表
39. *
40. * *************************************/
41. void MakeGraph(Graph *graph)
42. {
44.         int v1, v2;
45.         int i, j, k;
46.         printf("请输入图的顶点数n和边数e:\n");
47.         scanf("%d%d", &graph->vernum, &graph->edgenum);
48.         printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");
50.         for(i = 0; i < graph->vernum; i++)
51.         {
52.                 getchar();
53.                 scanf("%c", &graph->vertexs[i].vertex);
54.                 graph->vertexs[i].firstedge = NULL; //初始第一条边为空
55.         }
57.         printf("请输入每条边对应的两个顶点的序号(格式为i,j):\n");
58.         EdgeNode *p;
59.         for(k = 0; k < graph->edgenum; k++)
60.         {
61.                 scanf("%d,%d", &i, &j);  //读入边<vi,vj>的序号
62.                 p = (node *)malloc(sizeof(node)); //生成新的结点
63.                 p->adjvex = j - 1;
64.                 p->next = graph->vertexs[i - 1].firstedge;
65.                 graph->vertexs[i - 1].firstedge = p;
66.         }
67. }
69. /***************************************
70. *
71. * 广度优先遍历
72. *
73. * *************************************/
74. void BFS(Graph *graph)
75. {
76.         int i, j, k;
77.         queue<int> q;
78.         EdgeNode *p;
79.         for(i = 0; i < graph->vernum; i++) //初始化访问标识数组
80.                 visited[i] = FALSE;
82.         for(i = 0; i < graph->vernum; i++)
83.         {
84.                 if(!visited[i])
85.                 {
86.                         visited[i] = TRUE;
87.                         printf("广度优先遍历:结点%c\n", graph->vertexs[i].vertex);
88.                         q.push(i); //入栈
89.                         while(!q.empty())
90.                         {
91.                                 j = q.front();
92.                                 q.pop();  //出栈
93.                                 p = graph->vertexs[j].firstedge;
94.                                 while(p)
95.                                 {
96.                                         if(!visited[p->adjvex])
97.                                         {
98.                                                 printf("广度优先遍历:结点%c\n", graph->vertexs[p->adjvex].vertex);
99.                                                 visited[p->adjvex] = TRUE;
100.                                                 q.push(p->adjvex);
101.                                         }
102.                                         p = p->next;
103.                                 }
104.                         }
105.                 }
106.         }
107. }
109. int main()
110. {
111.         Graph *graph = (Graph *)malloc(sizeof(Graph));
112.         MakeGraph(graph); //建立图的邻接表
113.         BFS(graph); //广度优先遍历
115.         return 0;
116. }

复制代码

图一中的图，运行上述程序得到的结果如图二。

图一