第 47 课：Prim 最小生成树
学习目标
通过学习本课，你将能够：
- 理解 Prim 算法的基本思想及其贪心策略
- 掌握使用优先队列（最小堆）优化 Prim 算法的方法
- 实现一个完整的 Prim 算法，并分析其时间复杂度
- 对比 Prim 算法与 Kruskal 算法，理解各自适用场景
核心概念
什么是 Prim 算法？
Prim 算法是另一种经典的最小生成树（MST） 算法。与 Kruskal 算法“从边入手”不同，Prim 算法采用“从点入手”的策略：从一个起始顶点开始，逐步扩展，每次选择连接树内与树外顶点的最小权重边，直到所有顶点都被包含在树中。
通俗比喻：想象你站在地图上的某个城市（起始点），每次你都会选择从你已经“占领”的城市集合出发，修一条最便宜的路连接到一个未占领的新城市，直到所有城市都被连通。
贪心策略
Prim 算法是一个典型的贪心算法。它的每一步都做出局部最优的选择（选择当前最小的连接边），并期望通过这些局部最优选择达到全局最优（最小生成树）。
与 Kruskal 的对比
| 特性 | Prim 算法 | Kruskal 算法 |
|---|---|---|
| 出发点 | 从一个顶点开始，逐步扩展树 | 从所有边中开始，逐步合并连通分量 |
| 数据结构核心 | 优先队列（最小堆） | 并查集 |
| 适用场景 | 稠密图（边数多） | 稀疏图（边数少） |
| 时间复杂度 | 使用堆优化后 O(E log V) | O(E log E) ≈ O(E log V) |
优先队列（最小堆）优化
朴素的 Prim 算法需要每次扫描所有边来找最小边，效率很低。使用优先队列可以高效地维护“连接树内与树外顶点的所有边”，并快速取出权重最小的边。这是 Prim 算法高效实现的关键。
代码示例
下面是一个使用优先队列优化的 Prim 算法 Python 实现。我们使用 heapq 作为优先队列。
import heapq
from collections import defaultdict
def prim_mst(graph, start=0):
"""
使用 Prim 算法计算图的最小生成树。
参数:
graph (dict): 图的邻接表表示。graph[u] 是列表 [(v, weight), ...]
start (int): 起始顶点
返回:
mst_edges (list): 最小生成树的边 [(u, v, weight), ...]
total_cost (int): 最小生成树的总权重
"""
# 初始化
visited = set() # 记录已访问（已在树中）的顶点
min_heap = [] # 优先队列，存储 (权重, 当前顶点, 父节点)
mst_edges = [] # 存储 MST 的边
total_cost = 0
# 从起始点开始
visited.add(start)
# 将起始点连接的所有边加入堆
for neighbor, weight in graph[start]:
heapq.heappush(min_heap, (weight, start, neighbor))
while min_heap and len(visited) < len(graph):
# 取出当前权重最小的边
weight, u, v = heapq.heappop(min_heap)
# 如果v已在树中，则跳过
if v in visited:
continue
# 将v加入树中
visited.add(v)
mst_edges.append((u, v, weight))
total_cost += weight
# 将v连接的所有边（指向未访问顶点的边）加入堆
for neighbor, w in graph[v]:
if neighbor not in visited:
heapq.heappush(min_heap, (w, v, neighbor))
# 检查图是否连通（是否所有顶点都已访问）
if len(visited) != len(graph):
print("警告：图不连通，只能得到最小生成森林！")
return None, total_cost
return mst_edges, total_cost
# 示例图（邻接表表示）
# 顶点: 0, 1, 2, 3, 4
graph = {
0: [(1, 2), (3, 6)],
1: [(0, 2), (2, 3), (3, 8), (4, 5)],
2: [(1, 3), (4, 7)],
3: [(0, 6), (1, 8), (4, 9)],
4: [(1, 5), (2, 7), (3, 9)]
}
mst, cost = prim_mst(graph, start=0)
if mst is not None:
print("Prim 最小生成树的边:")
for u, v, w in mst:
print(f" {u} -- {v} (权重: {w})")
print(f"总权重: {cost}")
输出预期:
Prim 最小生成树的边:
0 -- 1 (权重: 2)
1 -- 2 (权重: 3)
1 -- 4 (权重: 5)
0 -- 3 (权重: 6)
总权重: 16
实践练习
练习 1：实现朴素 Prim 算法
实现一个不使用优先队列的 Prim 算法（每次扫描所有边来找最小边），并验证其正确性。思考其时间复杂度。
# 提示：使用一个数组记录每个顶点到树的最小距离，类似 Dijkstra 算法。
def prim_naive(graph, start=0):
n = len(graph)
visited = [False] * n
min_dist = [float('inf')] * n
parent = [-1] * n
min_dist[start] = 0
mst_edges = []
total_cost = 0
for _ in range(n):
# 找未访问的顶点中 min_dist 最小的
u = -1
for i in range(n):
if not visited[i] and (u == -1 or min_dist[i] < min_dist[u]):
u = i
if min_dist[u] == float('inf'):
break # 图不连通
visited[u] = True
total_cost += min_dist[u]
if parent[u] != -1:
mst_edges.append((parent[u], u, min_dist[u]))
# 更新邻接顶点的距离
for v, w in graph[u]:
if not visited[v] and w < min_dist[v]:
min_dist[v] = w
parent[v] = u
return mst_edges, total_cost
# 使用示例图测试你的实现
练习 2：处理不连通图
修改上面的代码，使其在图不连通时，返回最小生成森林（即每个连通分量的最小生成树集合）。
练习 3：比较 Prim 与 Kruskal
给定一个稀疏图（例如 100 个顶点，150 条边）和一个稠密图（100 个顶点，4000 条边），分别用 Prim 和 Kruskal 算法计算最小生成树，比较它们的运行时间。记录并分析你的观察。
常见错误
-
忽略图的连通性：Prim 算法要求图连通。如果不连通，算法只能得到最小生成森林。应先检查或明确说明图是否连通。
-
堆中存储错误信息：在将边加入优先队列时，需要同时存储权重、起始顶点和目标顶点
(weight, from, to)。如果只存(weight, to)，则在取出时无法正确记录生成树的边。 -
混淆最小堆方向：Python 的
heapq实现的是最小堆。如果需要最大堆，需要对权重取负。在 Prim 算法中，我们总是需要最小堆。 -
忘记标记已访问顶点：必须在将顶点加入生成树后立即标记为已访问，否则会导致重复访问和环路。
-
错误的复杂度分析：朴素 Prim 是 O(V²)，适合稠密图。使用二叉堆优化的 Prim 是 O(E log V)，更适合稀疏图。要根据图的特点选择算法。
小结
本课我们学习了 Prim 算法，一种用于寻找最小生成树的贪心算法。
关键要点回顾：
- 核心思想：从单一顶点开始，每次选择连接树内与树外的最小权重边，逐步扩展生成树。
- 高效实现：使用优先队列（最小堆） 来动态维护候选边，将复杂度从 O(V²) 优化到 O(E log V)。
- 算法步骤：
- 初始化，将起始点加入树中，并将其所有邻接边加入堆。
- 循环：从堆中取出最小边，如果边的另一端未访问，则将其加入树。
- 将新加入顶点的所有邻接边（指向未访问顶点的）加入堆。
- 直到所有顶点被访问或堆为空。
- 适用场景：特别适合边稠密的图。对于边稀疏的图，Kruskal 算法可能更简单高效。
- 注意：Prim 算法要求图是连通的，否则得到的是最小生成森林。
掌握 Prim 算法不仅让你拥有了解决最小生成树问题的另一种利器，也加深了对贪心策略和优先队列应用的理解。下一课，我们将进入网络流的基础知识，探索图论中另一个强大的工具。