【数据结构】图的遍历（深度优先搜索、广度优先搜索）及简单路径问题（C语言）_c语言图的简单路径

图的遍历就是从图中的某个顶点出发，按某种方法对图中所有顶点访问且仅访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和关键路径等算法的基础。
为了保证图中各个顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此要为图设置一个访问标志数组visited[n]，用于标示图中每个顶点是否被访问过。
对于图的遍历，通常有两种方法，即深度优先搜索和广度优先搜索。这两种遍历方法对于无向图和有向图均适用。图的深度优先搜索和广度优先搜索结果均不唯一。

1. 深度优先搜索

深度优先搜索（Depth-First Search，DFS）是指按照深度方向搜索，它类似于树的先根遍历，是树的先根遍历的推广。

1.1 深度优先搜索步骤

深度优先搜索基本步骤：
① 从图中某个顶点v0出发，首先访问v0。
② 找出刚访问过顶点的第一个未被访问的邻接点，然后访问该顶点。以该顶点为新顶点，重复此步骤，直到刚访问过的顶点没有未被访问的邻接点为止。
③ 返回前一个访问过的且仍有未被访问过的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点；然后执行步骤②。
示例：

首先访问A，从A出发；
（1）A未访问的邻接点有B、D、E，首先访问B；
（2）B未访问的邻接点有C、D，首先访问C；
（3）C未访问的邻接点为F，访问F；
（4）F没有未访问的邻接点，回溯到C；
（5）C没有未访问的邻接点，回溯到B；
（6）B未访问的邻接点为D，访问D；
（7）D未访问的邻接点为G，访问G；
（8）G未访问的邻接点有E、H，首先访问E；
（9）E没有未访问的邻接点，回溯到G；
（10）G未访问的邻接点为H，访问H；
（11）H未访问的邻接点为I，访问I；
（12）I没有未访问的邻接点，回溯到H；
（13）H没有未访问的邻接点，回溯到G；
（14）G没有未访问的邻接点，回溯到D；
（15）D没有未访问的邻接点，回溯到B；
（16）B没有未访问的邻接点，回溯到A；
至此，深度优先搜索结束，相应的访问序列为：A，B，C，F，D，G，E，H，I；
上图中所有顶点加上标有黑色箭头的边，构成一棵以A为根的树，称为深度优先搜索树。
注意：当一个顶点有多个未被访问的邻接点时，选择作为下一次访问的点的顺序可能不一样，因此图的深度优先搜索结果不唯一！

1.2 邻接矩阵方式实现深度优先搜索连通图

用邻接矩阵方式实现深度优先搜索连通图

/*用邻接矩阵方式实现深度优先搜索*/
int visited[MAX_VERTEX_NUM] = {
    0 };			//访问标志数组
void DepthFirstSearch(AdjMatrix G, int v0) {
   
	printf("%c ", G.vertex[v0]);
	visited[v0] = 1;							//置1表示已访问过
	for (int i = 0; i < G.vexnum; i++) {
   
		if (!visited[i] && G.arcs[v0][i].adj == 1)
			DepthFirstSearch(G, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

完整实现代码

# include<stdio.h>
# define MAX_VERTEX_NUM 20			//最多顶点个数

/*图的邻接矩阵表示法*/
typedef int AdjType;
typedef char VertexData;
typedef struct ArcNode {
   
	AdjType adj;							//无权图用1或0表示是否相邻，带权图则为权值类型
}ArcNode;
typedef struct {
   
	VertexData vertex[MAX_VERTEX_NUM];		//顶点向量
	ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
	int vexnum, arcnum;						//图的顶点数和弧数
}AdjMatrix;

/*求顶点位置*/
int LocateVertex(AdjMatrix* G, VertexData v) {
   
	int k;
	for (k = 0; k < G->vexnum; k++) {
   
		if (G->vertex[k] == v)
			break;
	}
	return k;
}

/*创建无向图的邻接矩阵*/
int CreateAdjMatrix(AdjMatrix* G) {
   
	int i, j, k;
	VertexData v1, v2;
	printf("输入图的顶点数和弧数：");			//输入图的顶点数和弧数
	scanf("%d%d", &G->vexnum, &G->arcnum);
	for (i = 0; i < G->vexnum; i++) {
   		//初始化邻接矩阵
		for (j = 0; j < G->vexnum; j++)
			G->arcs[i][j].adj = 0;
	}
	printf("输入图的顶点：");
	for (i = 0; i < G->vexnum; i++)			//输入图的顶点
		scanf(" %c", &G->vertex[i]);
	for (k = 0; k < G->arcnum; k++) {
   
		printf("输入第%d条弧的两个顶点：", k + 1);
		scanf(" %c %c", &v1, &v2);			//输入一条弧的两个顶点
		i = LocateVertex(G, v1);
		j = LocateVertex(G, v2);
		G->arcs[i][j].adj = 1;				//建立对称弧
		G->arcs[j][i].adj = 1;
	}
}

/*用邻接矩阵方式实现深度优先搜索*/
int visited[MAX_VERTEX_NUM] = {
    0 };			//访问标志数组
void DepthFirstSearch(AdjMatrix G, int v0) {
   
	printf("%c ", G.vertex[v0]);
	visited[v0] = 1;							//置1表示已访问过
	for (int i = 0; i < G.vexnum; i++) {
   
		if (!visited[i] && G.arcs[v0][i].adj == 1)
			DepthFirstSearch(G, i);
	}
}

int main() {
   
	AdjMatrix G;
	CreateAdjMatrix(&G);
	printf("\n深度优先搜索：");
	DepthFirstSearch(G, 0);
	return 0;
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

运行结果

1.3 邻接表方式实现深度优先搜索连通图

用邻接表方式实现深度优先搜索连通图

/*用邻接表方式实现深度优先搜索*/
int visited[MAX_VERTEX_NUM] = {
    0 }
1
2