数据结构与算法 / 系统课时
Kruskal 怎么构造最小生成树
Kruskal 怎么构造最小生成树
当图的成本都落在边上时,Kruskal 的核心策略很直接:先看最便宜的边,只要加入它不会形成环,就把它收入生成树。并查集负责快速判断“是否成环”,最终得到总权重最小的连通骨架。
学习目标
- 理解 Kruskal 为什么按边权从小到大选择安全边
- 用并查集实现最小生成树并计算总权重
- 能判断图不连通时为什么无法得到生成树
从最小边开始选安全边
最小生成树需要连接全部 个顶点,并且恰好包含 条边。Kruskal 先把所有边按权重升序排序,然后依次检查:若一条边连接的是两个不同连通分量,就加入它并合并分量;若两端已经连通,加入后会形成环,因此跳过。

关键点是“只在不同连通分量之间加边”。这样每次选中的都是当前能连接两个分量的最小权边,不会破坏最优性,同时并查集把环检测从遍历图降成了非常便宜的集合查询。
完整实现
下面使用边列表 (weight, u, v)。每次成功合并就累计权重,并记录选中的边;当已选边数达到 n - 1 时可以提前结束。
python
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n + 1))
self.size = [1] * (n + 1)
def find(self, x: int) -> int:
if self.parent[x] != x:
# 路径压缩减少后续根节点查询成本。
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a: int, b: int) -> bool:
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
# 按大小合并,避免并查集树退化。
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def kruskal(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, list[tuple[int, int, int]]]:
uf = UnionFind(n)
total = 0
chosen = []
for weight, u, v in sorted(edges):
# 只有连接两个不同分量的边才是安全边。
if uf.union(u, v):
total += weight
chosen.append((weight, u, v))
if len(chosen) == n - 1:
break
if len(chosen) != n - 1:
raise ValueError("图不连通,无法构造最小生成树")
return total, chosen
if __name__ == "__main__":
edges = [
(1, 1, 2),
(4, 1, 3),
(2, 2, 3),
(5, 2, 4),
(3, 3, 4),
]
total, chosen = kruskal(4, edges)
print(total)
print(chosen)预期输出
text
6
[(1, 1, 2), (2, 2, 3), (3, 3, 4)]按权重 1、2、3 选中的三条边已经连接四个顶点,总权重为 6。后续更重的边无需再检查,因为一棵包含四个顶点的生成树只需要三条边。
为什么它能保持最优
可以把当前已经形成的若干连通分量看成多个块。对于任意一个块,要把它和外部连接起来,跨越这个切分的最轻边一定存在于某棵最小生成树中。Kruskal 每次选择的正是某两个分量之间当前可用的最轻安全边,因此不断合并后仍能保持最优。
同权重边的处理顺序可能不同,所以最小生成树不一定唯一;但只要选择规则始终是不成环的最小权边,得到的总权重仍然是最小的。
复杂度与失败条件
排序是主要成本,时间复杂度为 ;之后的并查集操作总计约为 ,通常低于排序成本。空间复杂度为 ,其中边列表占 ,并查集占 。
如果扫描完全部边后仍不足 条已选边,说明原图不连通,只能得到最小生成森林,不能得到覆盖全部顶点的最小生成树。工程上应明确区分这两种结果,而不是把不完整的边集误当成 MST。
按自己的节奏,确认真正理解。