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

winston

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

深度优先搜索(Depth First Search)

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

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

2. #include <cstdlib>
4. #define VERTEXNUM 100 //顶点个数
5. typedef char VertexType;
6. typedef int EdgeType;
7. typedef enum{FALSE, TRUE} Boolean;
8. Boolean visited[VERTEXNUM];
10. /***************************************
11. *
12. * 邻接表存储结构
13. *
14. * *************************************/
15. typedef struct node
16. {
17.         int adjvex; //顶点位置
18.         struct node *next; //指向下一条边的指针
19. }EdgeNode;
21. typedef struct vnode
22. {
23.         VertexType vertex; //顶点信息
24.         EdgeNode *firstedge; //指向第一条依附该顶点的边的指针
25. }AdjList[VERTEXNUM];
27. typedef struct
28. {
29.         AdjList vertexs; //邻接表
30.         int vernum, edgenum; //图中当前的顶点和边数
31. }Graph;
33. /***************************************
34. *
35. * 建立图的邻接表
36. *
37. * *************************************/
38. void MakeGraph(Graph *graph)
39. {
41.         int v1, v2;
42.         int i, j, k;
43.         printf("请输入图的顶点数n和边数e:\n");
44.         scanf("%d%d", &graph->vernum, &graph->edgenum);
45.         printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");
47.         for(i = 0; i < graph->vernum; i++)
48.         {
49.                 getchar();
50.                 scanf("%c", &graph->vertexs[i].vertex);
51.                 graph->vertexs[i].firstedge = NULL; //初始第一条边为空
52.         }
54.         printf("请输入每条边对应的两个顶点的序号(格式为i,j):\n");
55.         EdgeNode *p;
56.         for(k = 0; k < graph->edgenum; k++)
57.         {
58.                 scanf("%d,%d", &i, &j);  //读入边<vi,vj>的序号
59.                 p = (node *)malloc(sizeof(node)); //生成新的结点
60.                 p->adjvex = j - 1;
61.                 p->next = graph->vertexs[i - 1].firstedge;
62.                 graph->vertexs[i - 1].firstedge = p;
63.         }
64. }
66. /***************************************
67. *
68. * 深度优先遍历
69. *
70. * *************************************/
71. void DFSTraverse(Graph *graph, int v)
72. {
73.         visited[v] = TRUE;
74.         printf("深度遍历:结点%c\n", graph->vertexs[v].vertex);
75.         EdgeNode *p = graph->vertexs[v].firstedge;
76.         while(p != NULL)
77.         {
78.                 if(!visited[p->adjvex])
79.                         DFSTraverse(graph, p->adjvex);
80.                 p = p->next;
81.         }
82. }
84. void DFS(Graph *graph)
85. {
86.         int i;
87.         for(i = 0; i < graph->vernum; i++)
88.                 visited[i] = FALSE;
90.         for(i = 0; i < graph->vernum; i++)
91.                 if(!visited[i])
92.                         DFSTraverse(graph, i);
93. }
95. int main()
96. {
97.         Graph *graph = (Graph *)malloc(sizeof(Graph));
98.         MakeGraph(graph); //建立图的邻接表
99.         DFS(graph); //深度优先遍历
101.         return 0;
102. }

复制代码

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

图一