第10章图的遍历与应用算法

当前位置:

首页 > 编程开发 > 数据结构 >

第10章图的遍历与应用算法

第10章图的遍历与应用算法
10.1 图的遍历算法
图的遍历是从图中某一顶点出发，按某种规则访问图中所有顶点，且每个顶点仅被访问一次的过程。遍历是图算法的基础，常用于路径查找、连通性分析、拓扑排序等场景。常用的遍历方法有深度优先搜索（DFS）和广度优先搜索（BFS）。
10.1.1 深度优先搜索（DFS）
基本思想
DFS的核心是“深度优先”——从起点出发，沿着一条路径尽可能深入访问，直到无法继续（所有邻接顶点均已访问），再回溯到上一个未探索完的顶点，继续深入。类比“走迷宫时，遇到岔路选一条走到头，走不通再退回上一个岔路”。
遍历规则：
1.访问起点顶点 vvv，标记为“已访问”；
2.递归地对 vvv 的所有未访问邻接顶点执行DFS；
3.若所有邻接顶点均已访问，则回溯。
无向图的DFS示例
以图10-1的无向图为例，起点为A，DFS遍历过程如下：
图10-1 无向图DFS示例

	A --- B --- D 
	| | 
	| | 
	C -----

遍历步骤：
1.访问A（标记[A]），邻接顶点B、C未访问，任选B深入；
2.访问B（标记[B]），邻接顶点A（已访问）、C、D未访问，任选C深入；
3.访问C（标记[C]），邻接顶点A（已访问）、B（已访问），回溯到B；
4.B的未访问邻接顶点D，访问D（标记[D]），邻接顶点B（已访问），回溯到B；
5.B所有邻接顶点已访问，回溯到A；
6.A所有邻接顶点已访问，遍历结束。
遍历序列：A→B→C→D（或A→C→B→D，取决于邻接顶点的访问顺序）。
实现方式
DFS可通过递归（隐式栈）或非递归（显式栈）实现，以下基于邻接表存储结构（无向图）：

递归实现
python

	def dfs_recursive(graph, v, visited, result): 
	"""DFS递归实现（无向图）""" 
	visited[v] = True # 标记为已访问 
	result.append(v) # 记录遍历序列 
	# 遍历所有未访问的邻接顶点 
	for neighbor in graph.adj[v]: 
	if not visited[neighbor]: 
	dfs_recursive(graph, neighbor, visited, result) 
	
	def dfs(graph, start): 
	"""DFS入口函数，返回遍历序列""" 
	visited = [False] * graph.num_vertices # 访问标记数组 
	result = [] 
	dfs_recursive(graph, start, visited, result) 
	return result

非递归实现（栈）
递归本质是利用系统栈，非递归实现需显式使用栈存储待访问顶点：
python

	def dfs_iterative(graph, start): 
	"""DFS非递归实现（栈，无向图）""" 
	visited = [False] * graph.num_vertices 
	result = [] 
	stack = [start] # 栈初始化，起点入栈 
	while stack: 
	v = stack.pop() # 弹出栈顶顶点 
	if not visited[v]: 
	visited[v] = True 
	result.append(v) 
	# 邻接顶点逆序入栈（保证按原顺序访问） 
	for neighbor in reversed(graph.adj[v]): 
	if not visited[neighbor]: 
	stack.append(neighbor) 
	return result

有向图的DFS
有向图的DFS与无向图类似，但需注意邻接顶点仅为出边指向的顶点。例如图10-2的有向图，起点A的DFS序列可能为A→B→C→D。
图10-2 有向图DFS示例

	A → B → C → D 
	↑ 
	| 
	←

DFS的应用
连通分量分析：遍历完一个连通分量后，若图中仍有未访问顶点，可开启新的DFS，统计连通分量数量；
判断回路：遍历中若遇到已访问且非父顶点的邻接顶点，则存在回路（无向图）；
拓扑排序（有向无环图）：DFS后按顶点完成时间逆序排列，得到拓扑序列。
10.1.2 广度优先搜索（BFS）
基本思想
BFS的核心是“广度优先”——从起点出发，优先访问所有距离为1的邻接顶点（同一层），再访问距离为2的邻接顶点（下一层），以此类推。类比“水滴扩散”或“层次遍历”。
遍历规则：
1.访问起点顶点 vvv，标记为“已访问”，加入队列；
2.队列非空时，出队顶点 uuu，访问其所有未访问邻接顶点，标记后入队；
3.重复步骤2，直至队列为空。
无向图的BFS示例
以图10-1的无向图为例，起点为A，BFS遍历过程如下：
遍历步骤：
1.访问A（标记[A]），入队[A]；
2.出队A，访问未访问邻接顶点B、C（标记[B]、[C]），入队[B, C]；
3.出队B，访问未访问邻接顶点D（标记[D]），入队[C, D]；
4.出队C，邻接顶点A、B已访问，无新顶点入队；
5.出队D，邻接顶点B已访问，无新顶点入队；
6.队列为空，遍历结束。
遍历序列：A→B→C→D（或A→C→B→D，取决于邻接顶点的入队顺序）。
实现方式
BFS通过队列实现，以下基于邻接表存储结构（无向图）：
python

	def bfs(graph, start): 
	"""BFS实现（无向图）""" 
	visited = [False] * graph.num_vertices 
	result = [] 
	queue = [start] # 队列初始化，起点入队 
	visited[start] = True # 起点标记为已访问 
	while queue: 
	u = queue.pop(0) # 出队（队首） 
	result.append(u) 
	# 遍历u的所有未访问邻接顶点，入队并标记 
	for v in graph.adj[u]: 
	if not visited[v]: 
	visited[v] = True 
	queue.append(v) 
	return result

BFS的应用
无权图最短路径：BFS的层次特性保证，从起点到其他顶点的路径长度（边数）为最短；
连通分量分析：与DFS类似，可统计非连通图的连通分量；
迷宫最短路：模拟迷宫探索，优先找到最短路径。
10.2 最短路径算法
最短路径是图论中的经典问题，目标是找到两顶点间权值之和最小的路径（带权图）。常见算法有单源最短路径的Dijkstra算法和多源最短路径的Floyd-Warshall算法。
10.2.1 Dijkstra算法（单源最短路径）
基本思想
Dijkstra算法用于求解带权无负权图中，从起点（单源）到其他所有顶点的最短路径。核心是“贪心策略”：维护一个“已确定最短路径的顶点集”，每次从剩余顶点中选择距离起点最近的顶点加入集合，并更新其邻接顶点的距离。
步骤：
1.初始化：起点距离为0，其他顶点距离为∞，距离数组dist[]，访问标记数组visited[]；
2.未访问顶点中，选择距离最小的顶点u，标记为已访问；
3.对u的所有邻接顶点v，若dist[v] > dist[u] + weight(u,v)，则更新dist[v] = dist[u] + weight(u,v)；
4.重复步骤2~3，直至所有顶点均被访问。
示例
以图10-3的带权无向图为例，起点为A，求解A到各顶点的最短路径：
图10-3 带权无向图（权值为距离）

	A ---3--- B ---2--- D 
	| | 
	| | 
	4 1 
	| | 
	C --------

邻接表（顶点0:A, 1:B, 2:C, 3:D）：
python

	adj = [ 
	[(1,3), (2,4)], # A的邻接顶点：B(3), C(4) 
	[(0,3), (3,2), (2,1)], # B的邻接顶点：A(3), D(2), C(1) 
	[(0,4), (1,1)], # C的邻接顶点：A(4), B(1) 
	[(1,2)] # D的邻接顶点：B(2) 
	]

Dijkstra步骤：
初始化：dist = [0, ∞, ∞, ∞]，visited = [F,F,F,F]
第1轮：选A（dist=0），更新邻接顶点B(3)、C(4) → dist = [0,3,4,∞]
第2轮：选B（dist=3），更新邻接顶点D(3+2=5)、C(3+1=4 < 4，不更新) → dist = [0,3,4,5]
第3轮：选C（dist=4），邻接顶点均已访问，无更新
第4轮：选D（dist=5），邻接顶点均已访问，无更新
结果：A到各顶点最短距离：A(0)、B(3)、C(4)、D(5)。
实现（优先队列优化）
使用优先队列（最小堆）快速选择距离最小的顶点，时间复杂度优化至 O((n+e)log⁡n)O((n+e)log n)O((n+e)logn)：
python

	import heapq 
	
	def dijkstra(adj, start, num_vertices): 
	"""Dijkstra算法（单源最短路径）""" 
	INF = float('inf') 
	dist = [INF] * num_vertices # 距离数组 
	dist[start] = 0 
	heap = [] 
	heapq.heappush(heap, (0, start)) # (距离, 顶点)入堆 
	
	while heap: 
	current_dist, u = heapq.heappop(heap) # 弹出距离最小的顶点 
	if current_dist > dist[u]: # 已处理过的顶点，跳过 
	continue 
	# 更新邻接顶点距离 
	for v, weight in adj[u]: 
	if dist[v] > dist[u] + weight: 
	dist[v] = dist[u] + weight 
	heapq.heappush(heap, (dist[v], v)) # 新距离入堆 
	return dist 
	
	# 测试 
	adj = [ 
	[(1,3), (2,4)], 
	[(0,3), (3,2), (2,1)], 
	[(0,4), (1,1)], 
	[(1,2)] 
	] 
	dist = dijkstra(adj, 0, 4) 
	print("A到各顶点最短距离:", dist) # 输出 [0, 3, 4, 5]

10.2.2 Floyd-Warshall算法（多源最短路径）
基本思想
Floyd-Warshall算法用于求解带权图（允许负权，但无负权回路）中，所有顶点对之间的最短路径。核心是“动态规划”：定义dist[k][i][j]为“经过前k个顶点中转，i到j的最短路径”，通过三重循环逐步更新距离矩阵。
状态转移方程：
dist[i][j]=min⁡(dist[i][j], dist[i][k]+dist[k][j]) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])
（即i到j的最短路径，要么不经过k，要么经过k，取两者最小值）
实现（邻接矩阵）
基于邻接矩阵存储，时间复杂度 O(n3)O(n^3)O(n3)，空间复杂度 O(n2)O(n^2)O(n2)：
python

	def floyd_warshall(adj_matrix): 
	"""Floyd-Warshall算法（多源最短路径）""" 
	n = len(adj_matrix) 
	# 初始化距离矩阵 
	dist = [row[:] for row in adj_matrix] 
	# 三重循环更新距离 
	for k in range(n): # 中转顶点 
	for i in range(n): # 起点 
	for j in range(n): # 终点 
	if dist[i][k] + dist[k][j] < dist[i][j]: 
	dist[i][j] = dist[i][k] + dist[k][j] 
	return dist 
	
	# 测试（图10-3的邻接矩阵，∞用999表示） 
	INF = 999 
	adj_matrix = [ 
	[0, 3, 4, INF], 
	[3, 0, 1, 2], 
	[4, 1, 0, INF], 
	[INF, 2, INF, 0] 
	] 
	dist = floyd_warshall(adj_matrix) 
	print("各顶点对最短路径矩阵:") 
	for row in dist: 
	print([x if x != INF else "∞" for x in row]) 
	# 输出： 
	# [0, 3, 4, 5] 
	# [3, 0, 1, 2] 
	# [4, 1, 0, 3] 
	# [5, 2, 3, 0]

10.3 最小生成树（MST）
最小生成树是带权连通无向图中，权值之和最小的生成树（含所有顶点，n-1条边，无回路）。常用于网络设计（如通信线路铺设，求最低成本）。
10.3.1 Prim算法
基本思想
Prim算法采用“加点法”：从任意顶点开始，逐步将“与当前生成树距离最近的顶点”加入树中，直至所有顶点加入。核心是维护一个“顶点到生成树的最小距离数组”。
步骤：
1.初始化：任选起点，距离数组lowest[]记录各顶点到生成树的最小距离（初始为起点邻接权值，其他为∞），visited[]标记生成树顶点；
2.未访问顶点中，选择lowest[]最小的顶点u，加入生成树；
3.更新u的邻接顶点v的lowest[v]：若weight(u,v) < lowest[v]，则lowest[v] = weight(u,v)；
4.重复步骤2~3，直至所有顶点加入生成树。
10.3.2 Kruskal算法
基本思想
Kruskal算法采用“加边法”：将所有边按权值升序排序，依次选边加入生成树，若加入后不形成回路（通过并查集判断），则保留该边，直至加入n-1条边。
步骤：
1.初始化：边按权值升序排序，并查集parent[]记录顶点所属集合，生成树边数count=0；
2.遍历排序后的边，对边(u,v)：
o若u和v属于不同集合（无回路），加入生成树，合并u和v的集合，count++；
o若count = n-1，停止遍历；
3.生成树边权之和为最小权值。
并查集（Union-Find）
Kruskal算法依赖并查集高效判断回路，基本操作：
find(u)：查找u的根节点；
union(u,v)：合并u和v的集合。
10.4 拓扑排序（有向无环图）
拓扑排序是对有向无环图（DAG）的顶点进行排序，使得所有有向边均从排序靠前的顶点指向靠后的顶点。常用于任务调度（如课程安排，先修课优先）。
步骤：
1.计算所有顶点的入度，入度为0的顶点入队；
2.队列非空时，出队顶点u，加入拓扑序列；
3.对u的所有邻接顶点v，入度减1，若v入度为0，入队；
4.重复步骤2~3，直至队列为空。若拓扑序列长度等于顶点数，则DAG无环；否则存在环。
10.5 总结
本章介绍了图的核心算法，包括：
遍历算法：DFS（深度优先，栈/递归）和BFS（广度优先，队列），是图算法的基础；
最短路径：Dijkstra（单源，贪心，无负权）和Floyd-Warshall（多源，动态规划，允许负权）；
最小生成树：Prim（加点法，适合稠密图）和Kruskal（加边法，适合稀疏图，需并查集）；
拓扑排序：针对DAG，解决任务依赖问题，通过入度表和队列实现。
这些算法需根据图的类型（有向/无向、带权/无权、有无负权）和场景（单源/多源、稠密/稀疏）选择，实际应用中需结合存储结构（邻接矩阵/邻接表）优化效率。
第10章图的遍历与应用算法
10.1 图的遍历
图的遍历是从某一顶点出发，按规则访问所有顶点且每个顶点仅访问一次的过程，是路径查找、连通性分析等应用的基础。常用遍历方法为深度优先搜索（DFS）和广度优先搜索（BFS）。
10.1.1 深度优先搜索（DFS）
基本思想
DFS遵循“深度优先”原则：从起点出发，沿一条路径深入访问，直至无法继续（邻接顶点均已访问），再回溯至未探索完的顶点继续。
核心步骤：
1.访问起点顶点 vvv，标记为“已访问”；
2.对 vvv 的每个未访问邻接顶点，递归执行DFS；
3.若所有邻接顶点均已访问，回溯至上层顶点。
无向图DFS示例
以图10-1无向图为例（顶点0_3对应AD），起点为0（A），邻接表为 adj = [[1,2], [0,2,3], [0,1], [1]]。
图10-1 无向图DFS示例

	0 --- 1 --- 3 
	| | 
	| | 
	2 -----

遍历过程：
访问0（标记）→ 递归访问1（邻接未访问顶点）；
访问1（标记）→ 递归访问2（邻接未访问顶点）；
访问2（标记）→ 邻接顶点0、1均已访问，回溯至1；
1的未访问邻接顶点3 → 访问3（标记），回溯至1；
1所有邻接顶点已访问，回溯至0，遍历结束。
遍历序列：0→1→2→3（邻接顶点访问顺序影响序列，如0→2→1→3也是可能序列）。
实现方式
基于邻接表存储，DFS可通过递归（隐式栈）或非递归（显式栈）实现。

递归实现
python

	def dfs_recursive(adj, v, visited, result): 
	"""DFS递归实现（邻接表存储，无向图）""" 
	visited[v] = True # 标记已访问 
	result.append(v) # 记录遍历序列 
	for neighbor in adj[v]: # 遍历所有邻接顶点 
	if not visited[neighbor]: 
	dfs_recursive(adj, neighbor, visited, result) 
	
	def dfs(adj, start): 
	"""DFS入口函数，返回遍历序列""" 
	n = len(adj) 
	visited = [False] * n 
	result = [] 
	dfs_recursive(adj, start, visited, result) 
	return result

非递归实现（显式栈）
python

	def dfs_iterative(adj, start): 
	"""DFS非递归实现（栈）""" 
	n = len(adj) 
	visited = [False] * n 
	result = [] 
	stack = [start] 
	while stack: 
	v = stack.pop() # 弹出栈顶顶点 
	if not visited[v]: 
	visited[v] = True 
	result.append(v) 
	# 逆序入栈，保证邻接顶点按原顺序访问 
	for neighbor in reversed(adj[v]): 
	if not visited[neighbor]: 
	stack.append(neighbor) 
	return result

复杂度分析
时间复杂度：O(n+e)O(n+e)O(n+e)（nnn 为顶点数，eee 为边数），每个顶点和边各访问一次；
空间复杂度：O(n)O(n)O(n)（递归栈或显式栈深度最坏为 nnn）。
10.1.2 广度优先搜索（BFS）
基本思想
BFS遵循“广度优先”原则：从起点出发，优先访问所有距离为1的邻接顶点（同一层），再访问距离为2的顶点（下一层），形成层次遍历。
核心步骤：
1.访问起点顶点 vvv，标记为“已访问”，入队；
2.队列非空时，出队顶点 uuu，访问其所有未访问邻接顶点，标记后入队；
3.重复步骤2，直至队列为空。
无向图BFS示例
以图10-1为例，起点为0（A）：
遍历过程：

访问0（标记），入队 [0]；
出队0，访问未访问邻接顶点1、2（标记），入队 [1,2]；
出队1，访问未访问邻接顶点3（标记），入队 [2,3]；
出队2，邻接顶点均已访问；出队3，邻接顶点均已访问；队列空，遍历结束。
遍历序列：0→1→2→3（层次顺序）。
实现方式（队列）
python

	def bfs(adj, start): 
	"""BFS实现（队列）""" 
	n = len(adj) 
	visited = [False] * n 
	result = [] 
	queue = [start] 
	visited[start] = True 
	while queue: 
	u = queue.pop(0) # 出队（FIFO） 
	result.append(u) 
	for v in adj[u]: # 访问所有未访问邻接顶点 
	if not visited[v]: 
	visited[v] = True 
	queue.append(v) 
	return result

复杂度分析
时间复杂度：O(n+e)O(n+e)O(n+e)（每个顶点和边各访问一次）；
空间复杂度：O(n)O(n)O(n)（队列最大长度为 nnn）。
10.2 最短路径算法
最短路径指带权图中两顶点间权值之和最小的路径。本节介绍单源最短路径的Dijkstra算法和多源最短路径的Floyd-Warshall算法。
10.2.1 Dijkstra算法（单源最短路径）
基本思想
适用于带权无负权图，求解从起点（单源）到其他所有顶点的最短路径。核心是“贪心策略”：维护距离数组 dist[]（dist[i] 为起点到 iii 的最短距离），每次选择 dist[] 最小的未访问顶点，更新其邻接顶点的距离。
算法步骤
1.初始化：dist[start] = 0，其他 dist[i] = ∞；visited[] 标记已确定最短路径的顶点。
2.选择顶点：在未访问顶点中，选择 dist[u] 最小的顶点 uuu，标记为已访问。
3.更新距离：对 uuu 的邻接顶点 vvv，若 dist[v] > dist[u] + weight(u,v)，则更新 dist[v] = dist[u] + weight(u,v)。
4.重复：执行步骤2~3，直至所有顶点均已访问。
示例
带权无向图（图10-2），顶点0~3，边权如图，起点为0：
图10-2 Dijkstra示例图

	0 ---3--- 1 ---2--- 3 
	| | 
	| | 
	4 1 
	| | 
	2 --------

邻接表（(邻接顶点, 权值)）：
python

	adj = [ 
	[(1,3), (2,4)], # 0的邻接顶点 
	[(0,3), (2,1), (3,2)], # 1的邻接顶点 
	[(0,4), (1,1)], # 2的邻接顶点 
	[(1,2)] # 3的邻接顶点 
	]

步骤：
初始化 dist = [0, ∞, ∞, ∞]，visited = [F,F,F,F]；
选择 u=0u=0u=0（dist=0），更新邻接顶点1（3）、2（4）→ dist = [0,3,4,∞]；
选择 u=1u=1u=1（dist=3），更新邻接顶点3（3+2=5）、2（3+1=4，不更新）→ dist = [0,3,4,5]；
选择 u=2u=2u=2（dist=4），邻接顶点均已访问；
选择 u=3u=3u=3（dist=5），邻接顶点均已访问；
结果：dist = [0,3,4,5]（起点0到各顶点最短距离）。
实现（优先队列优化）
使用优先队列（最小堆）快速选择 dist[] 最小的顶点，时间复杂度优化至 O((n+e)log⁡n)O((n+e)log n)O((n+e)logn)：
python

	import heapq 
	
	def dijkstra(adj, start, n): 
	"""Dijkstra算法（优先队列优化）""" 
	INF = float('inf') 
	dist = [INF] * n 
	dist[start] = 0 
	heap = [(0, start)] # (距离, 顶点)入堆 
	
	while heap: 
	current_dist, u = heapq.heappop(heap) 
	if current_dist > dist[u]: # 已处理过的顶点，跳过 
	continue 
	for v, w in adj[u]: # 更新邻接顶点距离 
	if dist[v] > dist[u] + w: 
	dist[v] = dist[u] + w 
	heapq.heappush(heap, (dist[v], v)) 
	return dist

10.2.2 Floyd-Warshall算法（多源最短路径）
基本思想
适用于带权图（允许负权，但无负权回路），求解所有顶点对之间的最短路径。核心是“动态规划”：定义 dist[k][i][j] 为“经过前 kkk 个顶点中转，iii 到 jjj 的最短路径”，通过三重循环更新距离矩阵。
状态转移方程：
dist[i][j]=min⁡(dist[i][j], dist[i][k]+dist[k][j]) ext{dist}[i][j] = min( ext{dist}[i][j], ext{dist}[i][k] + ext{dist}[k][j]) dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])
算法步骤
1.初始化：距离矩阵 dist 为邻接矩阵（dist[i][j] 为直接边权，无直接边时为 ∞∞∞）。
2.更新距离：对每个中转顶点 kkk，遍历所有顶点对 i,ji,ji,j，若经过 kkk 的路径更短，则更新 dist[i][j]。
实现（邻接矩阵）
python

	def floyd_warshall(adj_matrix): 
	"""Floyd-Warshall算法（多源最短路径）""" 
	n = len(adj_matrix) 
	dist = [row[:] for row in adj_matrix] # 复制邻接矩阵 
	
	for k in range(n): # 中转顶点 
	for i in range(n): # 起点 
	for j in range(n): # 终点 
	if dist[i][k] + dist[k][j] < dist[i][j]: 
	dist[i][j] = dist[i][k] + dist[k][j] 
	return dist

复杂度分析
时间复杂度：O(n3)O(n^3)O(n3)（三重循环）；
空间复杂度：O(n2)O(n^2)O(n2)（距离矩阵）。
10.3 最小生成树（MST）
最小生成树是带权连通无向图中，权值之和最小的生成树（含 nnn 个顶点、n−1n-1n−1 条边，无回路）。
10.3.1 Prim算法
基本思想
“加点法”：从任意顶点开始，逐步将“与当前生成树距离最近的顶点”加入树中，直至所有顶点加入。
核心步骤：
1.初始化：任选起点 vvv，lowest[u] 为顶点 uuu 到生成树的最小距离（初始为 vvv 的邻接权值，其他为 ∞∞∞），visited[] 标记生成树顶点。
2.选择顶点：在未访问顶点中，选择 lowest[u] 最小的顶点 uuu，加入生成树。
3.更新距离：对 uuu 的邻接顶点 vvv，若 weight(u,v) < lowest[v]，则更新 lowest[v] = weight(u,v)。
4.重复：执行步骤2~3，直至加入 n−1n-1n−1 条边。
实现
python

	def prim(adj, n): 
	"""Prim算法（最小生成树）""" 
	INF = float('inf') 
	lowest = [INF] * n # 顶点到生成树的最小距离 
	visited = [False] * n 
	lowest[0] = 0 # 起点（0号顶点）距离为0 
	mst_weight = 0 # MST总权值 
	
	for _ in range(n): # 迭代n次，选择n个顶点 
	# 选择lowest最小的未访问顶点u 
	u = -1 
	min_dist = INF 
	for i in range(n): 
	if not visited[i] and lowest[i] < min_dist: 
	min_dist = lowest[i] 
	u = i 
	if u == -1: # 图不连通，无MST 
	return -1 
	visited[u] = True 
	mst_weight += min_dist 
	
	# 更新u的邻接顶点距离 
	for v, w in adj[u]: 
	if not visited[v] and w < lowest[v]: 
	lowest[v] = w 
	return mst_weight

10.3.2 Kruskal算法
基本思想
“加边法”：将所有边按权值升序排序，依次选边加入生成树，若加入后不形成回路（通过并查集判断），则保留该边，直至加入 n−1n-1n−1 条边。
核心步骤：
1.初始化：边按权值升序排序；并查集 parent[] 记录顶点所属集合；生成树边数 count=0，总权值 mst_weight=0。
2.选边：遍历排序后的边 (u,v,w)(u,v,w)(u,v,w)：
o若 uuu 和 vvv 属于不同集合（无回路），加入生成树，mst_weight += w，count += 1，合并 uuu 和 vvv 的集合；
o若 count == n-1，停止遍历。
并查集（Union-Find）
用于高效判断回路（判断 uuu 和 vvv 是否连通）：
python

	class UnionFind: 
	def __init__(self, size): 
	self.parent = list(range(size)) 
	
	def find(self, x): # 查找根节点（路径压缩） 
	if self.parent[x] != x: 
	self.parent[x] = self.find(self.parent[x]) 
	return self.parent[x] 
	
	def union(self, x, y): # 合并集合（按秩合并） 
	x_root = self.find(x) 
	y_root = self.find(y) 
	if x_root == y_root: 
	return False # 已在同一集合，合并失败 
	self.parent[y_root] = x_root 
	return True

实现
python

	def kruskal(adj, n): 
	"""Kruskal算法（最小生成树）""" 
	edges = [] 
	for u in range(n): 
	for v, w in adj[u]: 
	if u < v: # 避免重复边（无向图） 
	edges.append((w, u, v)) 
	edges.sort() # 边按权值升序排序 
	
	uf = UnionFind(n) 
	mst_weight = 0 
	count = 0 
	
	for w, u, v in edges: 
	if uf.union(u, v): # 无回路，加入边 
	mst_weight += w 
	count += 1 
	if count == n-1: # 已选n-1条边，停止 
	break 
	return mst_weight if count == n-1 else -1 # 不连通返回-1

Prim与Kruskal对比

算法	思想	时间复杂度	适用场景
Prim	加点法	O(n2)O(n^2)O(n2)（邻接矩阵）	稠密图
Kruskal	加边法	O(elog⁡e)O(elog e)O(eloge)（排序边）	稀疏图

10.4 拓扑排序（有向无环图）
拓扑排序是对有向无环图（DAG）的顶点排序，使得所有有向边均从排序靠前的顶点指向靠后的顶点（如任务调度中，先修课优先于后续课）。
算法步骤
1.计算入度：统计所有顶点的入度（in_degree[]）。
2.入度为0的顶点入队：这些顶点无前置依赖，可优先排序。
3.处理队列：出队顶点 uuu，加入拓扑序列；对 uuu 的邻接顶点 vvv，入度减1，若 vvv 入度为0，入队。
4.判断结果：若拓扑序列长度为 nnn，则DAG无环；否则存在环（无法拓扑排序）。
实现
python

	def topological_sort(adj, n): 
	"""拓扑排序（DAG）""" 
	in_degree = [0] * n 
	for u in range(n): 
	for v in adj[u]: 
	in_degree[v] += 1 # 统计入度 
	
	queue = [] 
	for i in range(n): 
	if in_degree[i] == 0: 
	queue.append(i) # 入度为0的顶点入队 
	
	topo_order = [] 
	while queue: 
	u = queue.pop(0) 
	topo_order.append(u) 
	# 更新邻接顶点入度 
	for v in adj[u]: 
	in_degree[v] -= 1 
	if in_degree[v] == 0: 
	queue.append(v) 
	return topo_order if len(topo_order) == n else None # 有环返回None

10.5 总结本章介绍了图的核心算法，其思想和应用如下： 遍历算法：DFS（深度优先，栈/递归）和BFS（广度优先，队列）是图算法的基础； 最短路径：Dijkstra（单源，贪心，无负权）和Floyd（多源，动态规划，允许负权）； 最小生成树：Prim（加点法，稠密图）和Kruskal（加边法，稀疏图，需并查集）； 拓扑排序：基于入度和队列，解决DAG的依赖排序问题。实际应用中，需根据图的类型（有向/无向、带权/无权）和问题需求（单源/多源、稠密/稀疏）选择合适算法。

本站原创，转载请注明出处：https://www.xin3721.com/python3/python49271.html

栏目列表

首页 > 编程开发 > 数据结构 >

第10章 图的遍历与应用算法

第10章图的遍历与应用算法