图的深度优先搜索（邻接矩阵）

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

深度优先搜索(Depth First Search)

        深度优先搜索假设初始状态下图中所有顶点都未被访问，尝试优先搜索从图中某个顶点v出去，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v相连连的顶点都被访问到。如果此时图中还有没有访问到的顶点，则另选图中未被访问的某顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到。具体实现如下：

[cpp] view plaincopyprint?

1. #include <cstdio>  
2. #include <cstdlib>  
3.   
4. #define VERTEXNUM 100 //顶点个数  
5. typedef char VertexType; //顶点类型  
6. typedef int EdgeType;  
7. typedef enum{FALSE, TRUE} Boolean;  
8. Boolean visited[VERTEXNUM];  
9.   
10. /********************************************** 
11.  * 
12.  * 邻接矩阵存储结构 
13.  * 
14.  **********************************************/  
15. typedef struct  
16. {  
17.     VertexType vertexs[VERTEXNUM]; //顶点  
18.     EdgeType edges[VERTEXNUM][VERTEXNUM]; //邻接矩阵  
19.     int vernum, edgenum; //图中顶点和边数  
20. }Graph;  
21.   
22. /********************************************** 
23.  * 
24.  * 建立邻接矩阵 
25.  * 
26.  **********************************************/  
27. void MakeGraph(Graph *graph)  
28. {  
29.     int i, j, k;  
30.     printf("请输入顶点数和边数:\n");  
31.     scanf("%d%d", &graph->vernum, &graph->edgenum);  
32.     printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");  
33.     for(i = 0; i < graph->vernum; i++)  
34.     {  
35.         getchar();  
36.         scanf("%c", &graph->vertexs[i]);  
37.     }  
38.     for(i = 0; i < graph->vernum; i++) //初始化邻接矩阵  
39.     {  
40.         for(j = 0; j < graph->vernum; j++)  
41.         {  
42.             graph->edges[i][j] = 0;  
43.         }  
44.     }  
45.     printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n");  
46.     for(k = 0; k < graph->edgenum; k++)  
47.     {  
48.         scanf("%d,%d", &i, &j);  
49.         graph->edges[i - 1][j - 1] = 1; //(vi->vj)将edges[i][j]设置为1表示i,j间存在边  
50.     }  
51. }  
52.   
53. /********************************************** 
54.  * 
55.  * 深度优先搜索 
56.  * 
57.  **********************************************/  
58. void DFSTraverse(Graph *graph, int i)  
59. {  
60.     printf("深度优先遍历:顶点%c\n", graph->vertexs[i]);  
61.     visited[i] = TRUE;  
62.     for(int j = 0; j < graph->vernum; j++)  
63.     {  
64.         if(graph->edges[i][j] == 1 && !visited[j])  
65.             DFSTraverse(graph, j);  
66.     }  
67. }  
68.   
69. void DFS(Graph *graph)  
70. {  
71.     int i;  
72.     for(i = 0; i < graph->vernum; i++)  
73.         visited[i] = FALSE;  
74.     for(i = 0; i < graph->vernum; i++)  
75.         if(!visited[i])  
76.             DFSTraverse(graph, i);  
77. }  
78.   
79. int main()  
80. {  
81.     Graph *graph = (Graph *)malloc(sizeof(Graph));  
82.     MakeGraph(graph); // 建立图  
83.     DFS(graph); //深度优先搜索  
84.   
85.     return 0;  
86. }  

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

 

图一

图二

深度优先搜索遍历图的时间复杂度为O(n^2)，其中n为图中顶点个数。