算法：图的深度优先遍历（DepthFirstSearch ）
图的遍历和树的遍历类似，我们希望从图中某⼀顶点出发访遍图中其余顶点，且使每⼀个顶点仅被访问⼀次，这⼀过程就叫做图的遍历（Traver Graph)。图的遍历⽅法⼀般有两种，第⼀种是深度优先遍历（Depth First Search)，也有称为深度优先搜索，简称为DFS。第⼆种是《》，也有称为⼴度优先搜索，简称为BFS 。我们在《》中已经较为详细地讲述了深度优先搜索的策略，这⾥不再赘述。我们也可以把图当作⼀个迷宫，设定⼀个起始点，⾛遍所有图的顶点并打上标记，直到访问遍所有的顶点为⽌。如图7-5-2所⽰，需要注意的是结点I 是在从A->H，H->回溯->D，D->I 的时候被访问到的，⽽且我们是从A开始递归进⼊
保密义务下⾯的路径，所以会⼀直回溯到原点A为⽌表⽰遍历结束。
下⾯只给出邻接矩阵和邻接表存储⽅式时的图的深度优先遍历的算法代码，没有给出整体可供测试运
⾏的代码，其实只需要再写⼀个创建图的函数就可以进⾏整体测试了，可以参考《》和《》
⼀、如果我们使⽤的是邻接矩阵的⽅式，则代码如下：（改编⾃《⼤话数据结构》）
C++ Code
1
红眼病治疗方法2
3
4
5
6
7
8
9
10
11
12
13
考勤通报14
15
16 typedef char VertexType; /* 顶点类型应由⽤户定义 */ typedef int EdgeType; /* 边上的权值类型应由⽤户定义 */
#define MAXSIZE 9 /* 存储空间初始分配量 */ #define MAXEDGE 15 #define MAXVEX 9 typedef struct { VertexType vexs[MAXVEX]; /* 顶点表 */ EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，可看作边表 */ int numVertexes, numEdges; /* 图中当前的顶点数和边数 */ } MGraph; bool visited[MAXVEX]; /* 访问标志的数组 */
16
17
18
19
20
21
22
23
24
25
26
27
一看黄蝶一级录像
28
29
30
31
32
33
34
35
36 bool visited[MAXVEX]; /* 访问标志的数组 */
高中英语教案/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph MG, int i)
{
int j;超市宣传语
visited[i] = true;
cout << MG.vexs[i] << ' '; /* 打印顶点，也可以其它操作 */
for (j = 0; j < MG.numVertexes; j++)
望月怀远张九龄
if (MG.arc[i][j] == 1 && !visited[j])
DFS(MG, j); /* 对为访问的邻接顶点递归调⽤ */
}
/* 邻接矩阵的深度遍历操作 */
void DFSTraver(MGraph MG)
{
int i;
for (i = 0; i < MG.numVertexes; i++)
visited[i] = fal; /* 初始所有顶点状态都是未访问过状态 */ for (i = 0; i < MG.numVertexes; i++)
if (!visited[i])
DFS(MG, i); /* 对未访问过的顶点调⽤DFS，若是连通图，只会执⾏⼀次*/ }
遍历结果为： A B C D E F G H I (上图所⽰的图结构）
⼆、如果我们使⽤的是邻接表的⽅式，则代码如下：（改编⾃《⼤话数据结构》） C++ Code
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 /* 邻接表结构****************** */
typedef struct EdgeNode /* 边表结点 */
{
int adjvex; /* 邻接点域，存储该顶点对应的下标 */
int weight; /* ⽤于存储权值，对于⾮⽹图可以不需要 */
struct EdgeNode *next; /* 链域，指向下⼀个邻接点 */
} EdgeNode;
typedef struct VertexNode /* 顶点表结点 */
{
int in; //结点⼊度
char data; /* 顶点域，存储顶点信息 */
EdgeNode *firstedge; /* 边表头指针 */
二楼店面成功案例
} VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes, numEdges; /* 图中当前顶点数和边数 */
} graphAdjList, *GraphAdjList;
bool visited[MAXVEX]; /* 访问标志的数组 */
/* 邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;
visited[i] = true;
cout << GL->adjList[i].data << ' '; /* 打印顶点，也可以其它操作 */ p = GL->adjList[i].firstedge;
while (p)
{
if (!visited[p->adjvex])
DFS(GL, p->adjvex); /* 对为访问的邻接顶点递归调⽤ */
33
34
35
36
37
38
39
40
41
42
43
44
45
46 DFS(GL, p->adjvex); /* 对为访问的邻接顶点递归调⽤ */
p = p->next;
}
}
/* 邻接表的深度遍历操作 */
void DFSTraver(GraphAdjList GL)
{
int i;
for (i = 0; i < GL->numVertexes; i++)
visited[i] = fal; /* 初始所有顶点状态都是未访问过状态 */ for (i = 0; i < GL->numVertexes; i++)
if (!visited[i])
DFS(GL, i); /* 对未访问过的顶点调⽤DFS，若是连通图，只会执⾏⼀次*/ }
遍历结果为：A F G H E D I C B (上图所⽰的图结构）
由结果可以看出，因为我们采⽤了不同的存储⽅式，即使使⽤的是同样的深度优先搜索，遍历的结果也是不同的。
