数据结构（图遍历--广度优先遍历）

今天给大家说下图的广度优先遍历（BFS）：

    图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点 vi1,vi2, …, vi t，并均标记已访问过，然后再按照vi1,vi2, …, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

如图：

 

       首先发下用邻接链表法实现的广度优先遍历代码（如果不理解邻接链表法，请在本博客数据结构系列中查找，里面有详细介绍），代码是基于本博客数据结构系列讲解邻接链表法实现图写的，大家可以把这段代码加在那些代码中就可以运行：：

[cpp]  view plain  copy

1. static void recursive_bfs(TLGraph* tGraph, int v, int visited[], LGraph_Printf* pFunc)  
2. {  
3.     LinkQueue* queue = LinkList_Create();  
4.       
5.     if(NULL != queue)  
6.     {  
7.         LinkQueue_Append(queue, tGraph->v + v);  
8.           
9.         while(0 < LinkQueue_Length(queue))  
10.         {  
11.             int i = 0;  
12.               
13.             v = (LVertex**)LinkQueue_Retrieve(queue) - tGraph->v;  
14.               
15.             pFunc(tGraph->v[v]);  
16.               
17.             printf(", ");  
18.               
19.             for(i=0; i<tGraph->la[v]; i++)  
20.             {  
21.                 TListNode* node = (TListNode*)LinkList_Get(tGraph->la[v], i);  
22.                   
23.                 if(!visited[node->v])  
24.                 {  
25.                     LinkQueue_Append(queue, tGraph->v + node->v);  
26.                       
27.                     visited[node->v] = 1;  
28.                 }  
29.             }  
30.         }  
31.     }  
32.       
33.     LinkQueue_Destroy(queue);  
34. }  
35.   
36. void LGraph_BFS(LGraph* graph, int v, LGraph_Printf* pFunc)  
37. {  
38.     TLGraph* tGraph = (TLGraph*)graph;  
39.       
40.     int* visited = NULL;  
41.       
42.     int condition = (NULL != tGraph);  
43.     condition = condition && (0 <= v) && (v < tGraph->count);  
44.     condition = condition && (NULL != pFunc);  
45.     condition = condition && (NULL != (visited = (int*)calloc(tGraph->count, sizeof(int))));  
46.       
47.     if(condition)  
48.     {  
49.         int i = 0;  
50.           
51.         recursive_bfs(tGraph, v, visited, pFunc);  
52.           
53.         for(i=0; i<tGraph->count; i++)  
54.         {  
55.             if(!visited[i])  
56.             {  
57.                 recursive_bfs(tGraph, i, visited, pFunc);  
58.             }  
59.         }  
60.           
61.         printf("\n");  
62.     }  
63.       
64.     free(visited);  
65. }  

 

最后发下用邻接矩阵法实现的广度优先遍历代码（如果不理解邻接矩阵法，请在本博客数据结构系列中查找，里面有详细介绍），代码是基于本博客数据结构系列讲解邻接矩阵法实现图写的，大家可以把这段代码加在那些代码中就可以运行：