数据结构与算法 / 系统课时
Prim 和 Kruskal 怎么选
Prim 和 Kruskal 怎么选
Prim 和 Kruskal 都能求无向连通带权图的最小生成树,但它们处理边的方式完全不同。实际选型时,最重要的不是记住两个名字,而是看图的稀疏程度、输入形式以及手头是否适合使用堆或并查集。
学习目标
- 理解 Prim 与 Kruskal 构造最小生成树时的核心差异
- 能根据顶点数、边数和数据存储形式选择合适算法
- 能用代码验证两种算法得到相同的最小生成树权值
两种算法从哪里开始不同
Prim 始终维护一棵正在扩张的树。从任意顶点开始,每次选择一条连接“已进入生成树顶点”和“未进入顶点”的最小权边,把新顶点纳入树中。因此它关心的是当前树与外部之间有哪些候选边。
Kruskal 不从某个顶点出发,而是把全部边按权重从小到大处理。只要当前边连接的是两个不同连通分量,就接受这条边;如果两端已经连通,加入它会产生环,因此跳过。判断两端是否属于同一分量通常使用并查集。
两者依据的都是最小生成树的割性质,但维护状态不同:Prim 维护“一个不断扩大的连通区域”,Kruskal 维护“若干逐渐合并的连通分量”。
稀疏图和稠密图怎样影响选择
设顶点数为 ,边数为 。使用邻接表和二叉堆时,Prim 通常可以做到 ;Kruskal 的主要成本是排序全部边,为 ,并查集操作的额外成本接近线性。
如果图很稀疏,边本来就以边列表形式存在,Kruskal 往往最直接:排序后依次执行并查集即可。它不需要维护每个顶点到当前生成树的最小连接代价。
如果图非常稠密,例如接近完全图,边数约为顶点数平方量级,那么使用邻接矩阵实现的 Prim 可以直接做到 ,既避免显式排序大量边,实现也比较稳定。
| 场景 | 更自然的选择 | 原因 |
|---|---|---|
| 稀疏图、已有边列表 | Kruskal | 排序边后直接配合并查集 |
| 稠密图、邻接矩阵 | Prim | 实现简单,不必排序全部边 |
| 邻接表且希望从某点逐步扩张 | Prim | 堆可以只维护当前边界候选边 |
| 已有成熟并查集代码 | Kruskal | 环检测与分量合并非常直接 |
| 图可能不连通且需要最小生成森林 | Kruskal | 同一流程可自然得到各连通分量的生成树 |
用同一张图验证结果
下面的完整 Python 程序分别用堆实现 Prim、用并查集实现 Kruskal。示例图的最小生成树唯一权值为 6,因此两种实现即使选择边的先后顺序不同,总权值也应一致。
import heapq
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
('A', 'B', 1),
('A', 'C', 4),
('B', 'C', 2),
('B', 'D', 5),
('C', 'D', 1),
('C', 'E', 3),
('D', 'E', 2),
]
def prim(vertices, edges):
graph = {v: [] for v in vertices}
for u, v, w in edges:
graph[u].append((w, u, v))
graph[v].append((w, v, u))
visited = {vertices[0]}
heap = list(graph[vertices[0]])
heapq.heapify(heap)
mst = []
while heap and len(visited) < len(vertices):
w, u, v = heapq.heappop(heap)
if v in visited:
continue
visited.add(v)
mst.append((u, v, w))
for candidate in graph[v]:
if candidate[2] not in visited:
heapq.heappush(heap, candidate)
if len(visited) != len(vertices):
raise ValueError('graph is disconnected')
return mst
def kruskal(vertices, edges):
parent = {v: v for v in vertices}
rank = {v: 0 for v in vertices}
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return False
if rank[ra] < rank[rb]:
ra, rb = rb, ra
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1
return True
mst = []
for u, v, w in sorted(edges, key=lambda item: item[2]):
if union(u, v):
mst.append((u, v, w))
if len(mst) == len(vertices) - 1:
break
if len(mst) != len(vertices) - 1:
raise ValueError('graph is disconnected')
return mst
prim_mst = prim(vertices, edges)
kruskal_mst = kruskal(vertices, edges)
print('Prim:', prim_mst, 'weight =', sum(w for _, _, w in prim_mst))
print('Kruskal:', kruskal_mst, 'weight =', sum(w for _, _, w in kruskal_mst))预期输出
Prim: [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 1), ('D', 'E', 2)] weight = 6
Kruskal: [('A', 'B', 1), ('C', 'D', 1), ('B', 'C', 2), ('D', 'E', 2)] weight = 6当存在相同权重的候选边时,最小生成树可能不唯一,因此两种算法输出的边集合不一定完全相同;只要都包含 条边、保持连通且总权值达到最小即可。
选型时真正要检查什么
不要只按“Prim 适合稠密图、Kruskal 适合稀疏图”机械选择。工程实现还要看数据已经以什么形式存在。一个稀疏图如果已经维护了邻接表和优先队列,Prim 可能更省转换成本;一个规模不大的稠密图如果输入天然就是边列表,Kruskal 也完全可用。
还要区分连通图和非连通图。严格来说,非连通图不存在覆盖全部顶点的单棵最小生成树。Kruskal 在继续扫描边时会自然产生最小生成森林;Prim 若要达到同样效果,则需要对每个尚未访问的连通分量重新启动一次。
因此,选型可以归结为三个问题:边是否远少于顶点数平方、输入更接近邻接结构还是边列表、实现中更方便维护堆还是并查集。复杂度相近时,优先采用与现有数据结构最匹配、最容易验证正确性的方案。