综上，上图的DFS是按照如下顺序进行的：

A->B->D->H->E->H->D->B->A->C->F->G->F->C->A

    其中，红色部分代表首次访问，在这部分顶点被访问后，我们便将visited数组的对应元素设为true，表明这些顶点已经被访问过了，因此我们可以得到深度优先搜索得到的顺序为：

A->B->D->H->E->C->F->G

    深度优先搜索的代码实现如下：

[cpp] view plaincopy

1. /* 
2. 从序号为begin的顶点出发，递归深度优先遍历连通图Gp 
3. */  
4. void DFS(Graph Gp, int begin)  
5. {  
6.     //遍历输出序号为begin的顶点的数据域，并保存遍历信息  
7.     printf("%c ",Gp[begin].data);  
8.     visited[begin] = true;   
9.   
10.     //循环访问当前节点的所有邻接点（即该节点对应的链表）  
11.     int i;  
12.     for(i=first_vertex(Gp,begin); i>=0; i=next_vertex(Gp,begin,i))  
13.     {  
14.         if(!visited[i])  //对于尚未遍历的邻接节点，递归调用DFS  
15.             DFS(Gp,i);  
16.     }  
17. }   
18.   
19. /* 
20. 从序号为begin的节点开始深度优先遍历图Gp，Gp可以是连通图也可以是非连通图 
21. */  
22. void DFS_traverse(Graph Gp,int begin)  
23. {  
24.     int i;  
25.     for(i=0;i<NUM;i++)    //初始化遍历标志数组  
26.         visited[i] = false;   
27.   
28.     //先从序号为begin的顶点开始遍历对应的连通图  
29.     DFS(Gp,begin);  
30.     //如果是非连通图，该循环保证每个极大连通子图中的顶点都能被遍历到     
31.     for(i=0;i<NUM;i++)  
32.     {         
33.         if(!visited[i])  
34.             DFS(Gp,i);  
35.     }  
36. }  

[cpp] view plaincopy

1. /* 
2. 返回图Gp中pos顶点（序号为pos的顶点）的第一个邻接顶点的序号，如果不存在，则返回-1 
3. */  
4. int first_vertex(Graph Gp,int pos)  
5. {  
6.     if(Gp[pos].first)  //如果存在邻接顶点，返回第一个邻接顶点的序号  
7.         return  Gp[pos].first->vertex;  
8.     else              //如果不存在，则返回-1  
9.         return -1;  
10. }  
11.   
12. /* 
13. cur顶点是pos顶点（cur和pos均为顶点的序号）的其中一个邻接顶点， 
14. 返回图Gp中，pos顶点的（相对于cur顶点）下一个邻接顶点的序号,如果不存在，则返回-1 
15. */  
16. int next_vertex(Graph Gp,int pos,int cur)  
17. {  
18.     Node *p = Gp[pos].first; //p初始指向顶点的第一个邻接点  
19.     //循环pos节点对应的链表，直到p指向序号为cur的邻接点  
20.     while(p->vertex != cur)  
21.         p = p->pNext;  
22.   
23.     //返回下一个节点的序号  
24.     if(p->pNext)  
25.         return p->pNext->vertex;   
26.     else   
27.         return -1;  
28. }  

    广度优先搜索

    广度优先搜索（BFS）类似于树的层序遍历（如尚未掌握图的先序遍历，请移步这里：http://blog.csdn.net/ns_code/article/details/13169703）。其基本思想是：从头图中某个顶点v出发，访问v之后，依次访问v的各个未被访问的邻接点，而后再分别从这些邻接点出发，依次访问它们的邻接点，直到图中所有与v连通的顶点都已被访问。如果当前图只是需要遍历的非连通图的一个极大连通子图，则另选其他子图中的一个顶点，重复上述遍历过程，直到该非连通图中的所有顶点都被遍历完。很明显，跟树的层序遍历一样，图的广度优先搜索要用到队列来辅助实现。

    同样以上面的例子来分析，假设从A点开始遍历该图，根据图中顶点的存储关系，会按照下面的步骤来遍历该图：

    1、在访问完顶点A后，首先访问A的第一个邻接点B，而后访问A的第二个邻接点C；

    2、再根据顺序访问B的未被访问的邻接点，先访问D，后访问E；

    3、再根据顺序访问C的未被访问的邻接点，先访问F，在访问G；

    4、而后一次访问D、E、F、G等顶点的未被访问的邻接点；

    5、D的邻接点中，只有H未被访问，因地访问H；

    6、E、F、G、H等都没有未被访问的邻接点了，遍历到此结束。

A->B->C->D->E->F->G->H

    深度优先搜索的代码实现如下：

[cpp] view plaincopy

1. /* 
2. 从序号为begin的顶点开始，广度优先遍历图Gp，Gp可以是连通图也可以是非连通图 
3. */  
4. void BFS_traverse(Graph Gp,int begin)  
5. {  
6.     int i;  
7.     for(i=0;i<NUM;i++)    //初始化遍历标志数组  
8.         visited[i] = false;  
9.   
10.     //先从序号为begin的顶点开始遍历对应的连通图  
11.     BFS(Gp,begin);  
12.     //如果是非连通图，该循环保证每个极大连通子图中的顶点都能被遍历到     
13.     for(i=0;i<NUM;i++)  
14.     {   if(!visited[i])  
15.             BFS(Gp,i);        
16.     }  
17. }  
18.   
19. /* 
20. 从序号为begin的顶点开始，广度优先遍历连通图Gp 
21. */  
22. void BFS(Graph Gp,int begin)  
23. {  
24.     //遍历输出序号为begin的顶点的数据域，并保存遍历信息  
25.     printf("%c ",Gp[begin].data);  
26.     visited[begin] = true;   
27.   
28.     int i;  
29.     int pVertex;  //用来保存从队列中出队的顶点的序号  
30.     PQUEUE queue = create_queue();  //创建一个空的辅助队列  
31.     en_queue(queue, begin);          //首先将序号为begin的顶点入队  
32.     while(!is_empty(queue))  
33.     {  
34.         de_queue(queue,&pVertex);  
35.         //循环遍历，访问完pVertex顶点的所有邻接顶点,并将访问后的邻接顶点入队  
36.         for(i=first_vertex(Gp,pVertex); i>=0; i=next_vertex(Gp,pVertex,i))  
37.         {  
38.             if(!visited[i])  
39.             {  
40.                 printf("%c ",Gp[i].data);  
41.                 visited[i] = true;  
42.                 en_queue(queue,i);  
43.             }  
44.         }  
45.     }  
46.     //销毁队列，释放其对应的内存  
47.     destroy_queue(queue);  
48. }  

遍历结果

    按照上面的例子来构建图，而后采用如下代码测试DFS和BFS的输出结果：

[cpp] view plaincopy

1. /********************************** 
2. 图的BFS和DFS 
3. Author:兰亭风雨 Date:2014-02-20 
4. Email:zyb_maodun@163.com 
5. **********************************/  
6. #include<stdio.h>  
7. #include<stdlib.h>  
8. #include "data_structure.h"  
9.   
10. int main()  
11. {  
12.     Graph Gp = create_graph();  
13.   
14.     //深度优先遍历  
15.     printf("对图进行深度优先遍历：\n");  
16.     printf("从顶点A出发DFS的结果：");  
17.     DFS_traverse(Gp,0);  
18.     printf("\n");  
19.     printf("从顶点H出发DFS的结果：");  
20.     DFS_traverse(Gp,7);  
21.     printf("\n");  
22.     printf("从顶点E出发DFS的结果：");  
23.     DFS_traverse(Gp,4);  
24.     printf("\n");  
25.     printf("\n");  
26.   
27.     //广度优先遍历  
28.     printf("对图进行深度优先遍历：\n");  
29.     printf("从顶点A出发BFS的结果：");  
30.     BFS_traverse(Gp,0);  
31.     printf("\n");  
32.     printf("从顶点H出发BFS的结果：");  
33.     BFS_traverse(Gp,7);  
34.     printf("\n");  
35.     printf("从顶点E出发BFS的结果：");  
36.     BFS_traverse(Gp,4);  
37.     printf("\n");  
38.   
39.     int i;  
40.     //释放掉为每个单链表所分配的内存  
41.     for(i=0;i<NUM;i++)  
42.     {  
43.         free(Gp[i].first);  
44.         Gp[i].first = 0;  //防止悬垂指针的产生  
45.     }  
46.   
47.     //释放掉为顶点数组所分配的内存  
48.     free(Gp);  
49.     Gp = 0;  
50.     return 0;  
51. }  

完整代码下载

    完整的C语言实现代码下载地址：http://download.csdn.net/detail/mmc_maodun/6946859

本文地址：http://blog.csdn.net/ns_code/article/details/19617187