深度优先搜索算法的实践

如上篇博客所言，最近在学习数据结构中图的知识。按照书中的讲解和伪代码，我自己也编辑了个深度优先搜索算法。不过是用递归实现的。

本想也把广度优先搜索算法也一起做出来，却发现广度优先算法没有递归的实现。那就需要再一点时间去研究了。等下一篇博客贴出来。

 1 #include <iostream>
 2 #define MAX_VERTEX_NUM 21
 3 using namespace std;
 4  
 5 typedef struct Graph
 6 {
 7     int vex[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 8     int vexNum;
 9     int arsNum;
10     int visited[MAX_VERTEX_NUM];
11 }Graph;
12 
13 void init(Graph *G)
14 {
15     int i, j;
16     for (i = 1; i <= G->vexNum; ++i)
17     {
18         for (j = 1; j <= G->vexNum; ++j)
19         {
20             G->vex[i][j] = 0;
21         }
22         G->visited[i] = 0; 
23     }
24 }
25 void print(Graph *G)
26 {
27     int i, j;
28     for (i = 1; i <= G->vexNum; i++)
29     {
30         for (j = 1; j <= G->vexNum; j++)
31         {
32             printf("%d ", G->vex[i][j]);
33         }
34         printf("
");
35     }
36 }
37 
38 void creat(Graph *G)
39 {
40     int i;
41     cout << "please input the num of vex and ars:";
42     scanf("%d %d", &G->vexNum, &G->arsNum);
43     init(G);
44     for (i = 0; i < G->arsNum; ++i)
45     {
46         int ars1, ars2;
47         printf("please input the %d ars :", i+1);
48         scanf("%d %d", &ars1, &ars2);
49         G->vex[ars1][ars2] = 1;
50     }
51     print(G);
52 }
53 
54 void visit(Graph *G, int vex)
55 {
56     printf("the vex %d has been visited
", vex);
57     G->visited[vex] = 1;
58 }
59 
60 void DepthFirstSerch(Graph *G, int vex)
61 {
62     int i;
63     visit(G, vex);
64     for(i = 1; i <= G->vexNum; i++)
65     {
66         if(G->visited[i] == 0 && G->vex[vex][i] == 1)
67             DepthFirstSerch(G, i);
68     }
69 
70 }
71 
72 int main()
73 {
74     Graph G;
75     creat(&G);
76     DepthFirstSerch(&G, 1);
77     return 0;
78 }

运行结果如图

这个程序验证了课本中罗列的一个图的深度优先遍历顺序。（书中的ABCD 均有 1234代替）