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

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

广度优先搜索(Breadth First Search)

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

采用邻接表存储图的具体实现如下：

[cpp] view plaincopyprint?

1. #include <iostream>  
2. #include <queue>  
3. #include <cstdio>  
4. #include <cstdlib>  
5. using namespace std;  
6.   
7. #define VERTEXNUM 100 //顶点个数  
8. typedef char VertexType;  
9. typedef int EdgeType;  
10. typedef enum{FALSE, TRUE} Boolean;  
11. Boolean visited[VERTEXNUM];  
12.   
13. /*************************************** 
14.  * 
15.  * 邻接表存储结构  
16.  * 
17.  * *************************************/  
18. typedef struct node  
19. {  
20.     int adjvex; //顶点位置  
21.     struct node *next; //指向下一条边的指针  
22. }EdgeNode;  
23.   
24. typedef struct vnode  
25. {  
26.     VertexType vertex; //顶点信息  
27.     EdgeNode *firstedge; //指向第一条依附该顶点的边的指针  
28. }AdjList[VERTEXNUM];  
29.   
30. typedef struct  
31. {  
32.     AdjList vertexs; //邻接表  
33.     int vernum, edgenum; //图中当前的顶点和边数  
34. }Graph;  
35.   
36. /*************************************** 
37.  * 
38.  * 建立图的邻接表 
39.  * 
40.  * *************************************/  
41. void MakeGraph(Graph *graph)  
42. {  
43.   
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");  
49.   
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.     }  
56.   
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. }  
68.   
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;  
81.   
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. }  
108.   
109. int main()  
110. {  
111.     Graph *graph = (Graph *)malloc(sizeof(Graph));  
112.     MakeGraph(graph); //建立图的邻接表  
113.     BFS(graph); //广度优先遍历  
114.   
115.     return 0;  
116. }  

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

图一

图二