手工模拟图的各大常用算法。

1 图的遍历算法

1.1 BFS 算法（广度优先遍历）

【性质】

• 空间复杂度：O(|V|)（需要一个辅助队列）
• 采用邻接表的时间复杂度：O(|V|+|E|)
• 采用邻接矩阵的时间复杂度：O(|V|²)
• 遍历方法与树的层序遍历相同（不再给出手工模拟算法的过程）
• 非递归算法
• 用邻接矩阵存储的图，其广度优先生成树唯一；用邻接表存储的图，其广度优先生成树不唯一

【核心思想】

• 首先访问起始顶点 v
• 由 v 出发，依次访问 v 的各个未访问的邻接顶点 w1，w2，…，wi（将它们依次存入辅助队列）
• 由这些顶点 w1，w2，…，wi 出发（将它们依次出列），再依次访问它们的未访问的邻接顶点

【核心代码】

bool visited[MAX_VERTEX_NUM];	// 标记顶点的访问情况 
Queue Q;						// 辅助队列 

void BFSTraverse (Graph G){
	for (v = 0; v < G.vexnum; v++){
		visited[v] = FALSE;		// 初始化各顶点的访问情况为未访问 
	}
	InitQueue(Q); 				// 初始化辅助数列 Q 
	
// 考虑到非连通图，为防止一次调用 BFS 函数访问不到其他连通分量，检查一遍 visited 即可继续访问未访问的顶点 
// 考虑到非强连通图，有些顶点也是访问不到的，因此检查一遍 visited 即可继续访问未访问的顶点 
	for (v = 0; v < G.vexnum; v++){		
		if (visited[v] == FALSE)
			BFS(G, v);
	}
}

void BFS (Graph G, int v){
	visit(v);			// 访问顶点 
	visited[v] = TRUE;	// 设置该顶点为已访问过
	EnQueue(Q, v);		// 顶点 v 入队 
	
	while (!isEmpty(Q)){// 队列非空时 
		DeQueue(Q, v);		// 顶点 v 出队
		// 依次访问 v 的邻接点
		// FirstNeighbor(G,v)：求图 G 中顶点 v 的第一个邻接点
		// NextNeighbor(G,v,w)：图 G 中顶点 w 是顶点 v 的一个邻接点，返回除 w 外顶点 v 的下一个邻接点 
		for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
			if (visited[w] == FALSE){	// 若顶点 w 尚未访问 
				visit(w);			// 访问顶点
				visited[w] = TRUE;	// 设置该顶点为已访问过
				EnQueue(Q, w);		// 顶点 w 入队 
			}
		}
	}
}
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

1.2 DFS 算法（深度优先遍历）

【性质】

• 空间复杂度：O(|V|)（需要一个辅助递归工作栈）
• 采用邻接表的时间复杂度：O(|V|+|E|)
• 采用邻接矩阵的时间复杂度：O(|V|²)
• 遍历方法与树的先序遍历相同（不再给出手工模拟算法的过程）
• 递归算法
• 用邻接矩阵存储的图，其深度优先生成树唯一；用邻接表存储的图，其深度优先生成树不唯一

【核心思想】

• 访问起始顶点 v
• 由顶点 v 出发，访问与其邻接的未访问的第一个顶点 w1
• 再访问与 w1 邻接的未访问顶点 w11
• 不断重复以上过程，直到不能再向下访问时，回退到最近被访问的顶点，继续访问它的其它邻接顶点

【核心代码】

bool visited[MAX_VERTEX_NUM];	// 标记顶点的访问情况 

void DFSTraverse (Graph G){
	for (v = 0; v < G.vexnum; v++){
		visited[v] = FALSE;		// 初始化各顶点的访问情况为未访问 
	}
// 考虑到非连通图，为防止一次调用 DFS 函数访问不到其他连通分量，检查一遍 visited 即可继续访问未访问的顶点 
// 考虑到非强连通图，有些顶点也是访问不到的，因此检查一遍 visited 即可继续访问未访问的顶点 
	for (v = 0; v < G.vexnum; v++){		
		if (visited[v] == FALSE)
			DFS(G, v);
	}
}

void DFS (Graph G, int v){
	visit(v);			// 访问结点 
	visited[v] = TRUE;	// 设置该结点为已访问过 
	// 依次访问 v 的邻接点
	// FirstNeighbor(G,v)：求图 G 中顶点 v 的第一个邻接点
	// NextNeighbor(G,v,w)：图 G 中顶点 w 是顶点 v 的一个邻接点，返回除 w 外顶点 v 的下一个邻接点 
	for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
		if (visited[w] == FALSE)	// 若顶点 w 尚未访问 
			DFS(G, w);
	} 
}
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

2 最短路径问题

2.1 BFS 算法（求无权图的单源最短路径）

【核心思想】

• 注意到可以将无权图转换为根为顶点 i 的生成树。又因为广度优先生成树的高度一定小于等于深度优先生成树，所以对于广度优先生成树来说，它的根到其他顶点的距离一定是最短的。

【核心代码】

• 新增加两个数组：dist 和 path

bool visited[MAX_VERTEX_NUM];	// 标记顶点的访问情况 
int dist[MAX_VERTEX_NUM];		// 记录从源点（V0）到该点（Vi）的最短路径长度
int path[MAX_VERTEX_NUM];		// 路径上的前驱（存储到达 Vi 的前一个结点编号）
Queue Q;						// 辅助队列 

void BFSTraverse (Graph G){
	for (v = 0; v < G.vexnum; v++){
		visited[v] = FALSE;		// 初始化各顶点的访问情况为未访问 
		dist[v] = 999999;		// 初始化路径长度 
		path[v] = -1;			// 初始化路径上的顶点 v 的前驱顶点 
	}
	InitQueue(Q); 				// 初始化辅助数列 Q 
	
// 考虑到非连通图，为防止一次调用 BFS 函数访问不到其他连通分量，检查一遍 visited 即可继续访问未访问的顶点 
// 考虑到非强连通图，有些顶点也是访问不到的，因此检查一遍 visited 即可继续访问未访问的顶点 
	for (v = 0; v < G.vexnum; v++){		
		if (visited[v] == FALSE)
			BFS(G, v);
	}
}

void BFS_Min_Dist (Graph G, int v){
	dist[v] = 0;		// 从初始顶点 v 开始遍历，它的最短路径长度设置为 0 
	visited[v] = TRUE;	// 设置该顶点为已访问过
	EnQueue(Q, v);		// 顶点 v 入队 
	
	while (!isEmpty(Q)){// 队列非空时 
		DeQueue(Q, v);		// 顶点 v 出队
		// 依次访问 v 的邻接点
		// FirstNeighbor(G,v)：求图 G 中顶点 v 的第一个邻接点
		// NextNeighbor(G,v,w)：图 G 中顶点 w 是顶点 v 的一个邻接点，返回除 w 外顶点 v 的下一个邻接点 
		for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
			if (visited[w] == FALSE){	// 若顶点 w 尚未访问 
				dist[w] = dist[v] + 1;	// 路径长度加 1 
				path[w] = v; 			// 标记到达顶点 w 需要从顶点 v 过来 
				visited[w] = TRUE;		// 设置该顶点为已访问过
				EnQueue(Q, w);			// 顶点 w 入队 
			}
		}
	}
}
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

2.2 Dijkstra 算法（求带权图的单源最短路径）

【性质】

• 时间复杂度：O(|V|²)
• 基于贪心策略
• 不适用于带负权值的图
• 不适用于带负权回路的图

以下面有向图为例：

step0. 初始状态

• final 数组：标记各顶点是否已找到最短路径

• dist 数组：记录从源点（V0）到该点（Vi）的最短路径长度

• path 数组：路径上的前驱（存储到达 Vi 的前一个结点编号）

step1. 第一轮

上一步的表格：

【1】找到上一步中：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V4，令 final[i] = True，表示从 V0 到 Vi 的最短路径已确定。

• final 数组：

【2】检查所有邻接自 Vi = V4 的点，若其 final 值为 False，则对比 step0 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。

【2.1】对于 V1（原本 dist = 10， path = 0）：final 值为 False，从 V0–>V4–>V1 的路径长度为 5+3=8 < 10，所以需要更新其 dist = 8（表示从 V0 到 V1 的路径长度为 8，以下类似），path = 4（表示这条路径是从 V4 结点过来的，以下类似）；

【2.2】对于 V2（原本 dist = ∞， path = -1）：final 值为 False，从 V0–>V4–>V2 的路径长度为 5+9=14 < ∞，所以需要更新其 dist = 14，path = 4；

【2.3】对于 V3（原本 dist = ∞， path = -1）：final 值为 False，从 V0–>V4–>V3 的路径长度为 5+2=7 < ∞，所以需要更新其 dist = 7，path = 4。

• dist 数组：

• path 数组：

step2. 第二轮

上一步的表格：

【1】找到上一步中：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V3，令 final[i] = True，表示从 V0 到 Vi 的最短路径已确定。

• final 数组：

【2】检查所有邻接自 Vi = V3 的点（对应 dist = 7，path = 4），若其 final 值为 False，则对比 step1 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。

【2.1】对于 V0：final 值为 True。

【2.2】对于 V2（原本 dist = 14，path = 4）：final 值为 False，从 V0–>V4–>V3–>V2 的路径长度为 7+6=13 < 14，所以需要更新其 dist = 13，path = 3。

• dist 数组：

• path 数组：

step3. 第三轮

上一步的表格：

【1】找到上一步中：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V1，令 final[i] = True，表示从 V0 到 Vi 的最短路径已确定。

• final 数组：

【2】检查所有邻接自 Vi = V1 的点（对应 dist = 8，path = 4），若其 final 值为 False，则对比 step2 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。

【2.1】对于 V2（原本 dist = 13，path = 3）：final 值为 False，从 V0–>V4–>V1–>V2 的路径长度为 8+1=9 < 13，所以需要更新其 dist = 9，path = 1。

【2.2】对于 V4：final 值为 True。

• dist 数组：

• path 数组：

step4. 第四轮

上一步的表格：

【1】找到上一步中：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V2，令 final[i] = True，表示从 V0 到 Vi 的最短路径已确定。

• final 数组：

【2】检查所有邻接自 Vi = V2 的点（对应 dist = 13，path = 3），若其 final 值为 False，则对比 step2 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。

已经找不到其他未访问结点，算法结束，以下为最终结果：

• dist 数组：

• path 数组：

【应试】快速解答

2.3 Floyd 算法（求带权图的各顶点之间最短路径）

【性质】

• 时间复杂度：O(|V|³)
• 适用于带负权值的图
• 不适用于带负权回路的图

【注】可以使用单源最短路径算法解决每对顶点最短路径问题，例如可使用 Dijkstra 算法，轮流将每个结点当成源点，时间复杂度也为 O(|V|³)

【核心代码】

for (int k = 0; k < n; k++){  // 加入 Vk 作为中转站
  for (int i = 0; i < n; i++){  // 遍历整个邻接权值矩阵，i 为行，j 为列
    for (int j = 0; j < n; j++){
        if (A[i][j] > A[i][k] + A[k][j]){  // 从顶点 i 到顶点 j，经过 Vk 中转站的路径更短
            A[i][j] = A[i][k] + A[k][j];   // 更新路径长度
            path[i][j] = k;                // 记录中转顶点的编号
        }
    }
  }
}
1
2
3
4
5
6
7
8
9
10

以下面有向图为例：

step0. 初始状态（不允许在其他顶点中转）

• A^(-1)（从目前来看，各顶点之间的最短路径长度）

• path^(-1)（两个顶点之间的中转点）

step1. 第一轮（允许在顶点 V0 中转）

上一步中可以发现，如果加入了 V0 中转，则有：

A-1[2][1] = ∞ > A-1[2][0] + A-1[0][1] = 11

所以应改为：

• A⁽⁰⁾（从目前来看，各顶点之间的最短路径长度）

• path⁽⁰⁾（两个顶点之间的中转点）

step2. 第二轮（允许在顶点 V1 中转/加入顶点 V1 进行中转）

上一步中可以发现，如果在加入了 V0 中转的基础上，又加入了 V1 中转，则有：

A0[0][2] = 13 > A0[0][1] + A0[1][2] = 10

所以应改为：

• A⁽¹⁾（从目前来看，各顶点之间的最短路径长度）

• path⁽¹⁾（两个顶点之间的中转点）

step3. 第三轮（允许在顶点 V2 中转/加入顶点 V2 进行中转）

上一步中可以发现，如果在加入了 V0、V1 中转的基础上，又加入了 V2 中转，则有：

A1[1][0] = 13 > A1[1][2] + A1[2][0] = 9

所以应改为：

• A⁽²⁾（从目前来看，各顶点之间的最短路径长度）

• path⁽²⁾（两个顶点之间的中转点）

由于没有其他的顶点，因此算法结束。

根据以上两个矩阵：

• 从 V0 到 V2，在矩阵 A 中获知最短路径为 10，在矩阵 path 中获知路径是 V0–>V1–>V2；
• 从 V1 到 V0，在矩阵 A 中获知最短路径为 2，在矩阵 path 中获知路径是 V1–>V2–>V0；
• 以此类推。

较复杂的例子

如果要找从 V0 到 V4 的最短路径：

• 在矩阵 A 中得知 V0 到 V4 的最短路径长度为 4，在矩阵 path 中得知从 V0 到 V4 需经过 V3；
• 在矩阵 A 中得知 V0 到 V3 的最短路径长度为 3，在矩阵 path 中得知从 V0 到 V3 需经过 V2；
• 在矩阵 A 中得知 V0 到 V2 的最短路径长度为 1，在矩阵 path 中得知从 V0 到 V2 不需经过顶点；
• 在矩阵 A 中得知 V2 到 V3 的最短路径长度为 2，在矩阵 path 中得知从 V2 到 V3 需经过 V1；
• 在矩阵 A 中得知 V1 到 V3 的最短路径长度为 1，在矩阵 path 中得知从 V1 到 V3 不需要经过顶点；
• 最终，从 V0 到 V4 的最短路径是 4，路径为 V0–>V2–>V1–>V3–>V4。

3 最小生成树

【性质】

• 图的各边权值不相等时，其最小生成树不唯一
• 最小生成树的权值是唯一的
• 最小生成树的边数为顶点数减 1
• 以下两种算法均基于贪心策略

3.1 Prim 算法

使用 Prim 算法手工构造最小生成树的过程如下：

3.2 Kruskal 算法

使用 Kruskal 算法手工构造最小生成树的过程如下：

---EOF---