最小生成树

01 / 共享的机制

最小生成树是把一张带权无向图所有节点连起来的最便宜方式 ——恰好 N − 1 条边、无环、总权重最小。 两种经典构造方式:Kruskal按边权排序后从小到大走, 用并查集跳过任何会成环的边;Prim从某个节点出发,用最小堆不断把当前树的最便宜出边吸进来。

01 / 一句话本质
把所有边按权重升序排序,从小到大扫一遍,两端在不同分量的边就收下(用并查集判断); 其余的跳过 —— 它们会成环。收到 N − 1 条边时就停。
题目用并查集构造最小生成树V6E8
43124265012345按权重排序的边边 · w0 — 140 — 231 — 211 — 322 — 343 — 424 — 563 — 55
图:6 个节点,8 条边。生成树需要 5 条边。
步
0 / 16
已收下
0 / 5
总权重
—
0 / 16

02 / 模式骨架

# 输入:V 个节点,edges = [(u, v, w), …]sort(edges) by w ascparent[i] ← i # DSU 初始化mst ← []; total ← 0for (u, v, w) in edges:if find(u) ≠ find(v): # 两端属于不同分量union(u, v); mst.push((u, v, w)); total += wif len(mst) == V − 1: break# 否则:u、v 已经连通 → 跳过(会成环)return total if len(mst) == V − 1 else ∞ # 不连通

03 / 什么时候用这个模式

"最小生成树"
最经典的说法。当题目给你一张带权无向图并问「连通所有节点的最低代价子图」时 —— 就是 MST。 如果输入本身就是边列表,Kruskal 是首选。
"最便宜地连通所有节点"
LC 1135(连通 N 个城市的最小成本)。把所有城市连通的代价就等于 MST 的总权重。 对边按权重排序,跑 Kruskal,返回总和 —— 若收到的边不足 N − 1 条,则返回 −1。
"次小生成树"
LC 1489(关键边与伪关键边)。先求出一次 MST,再对每条边问:强制删除这条边,MST 总权重还能不变吗?强制包含呢? 每条边再跑两次 Kruskal,就能把所有边干净地分为关键、伪关键、或都不是。
"连接所有点的最小费用"
LC 1584。构造完全图(每对点之间的曼哈顿距离),把全部 O(N²) 条边排序, 跑 Kruskal。对这种稠密图,可以拿 Kruskal 的边中心思路与 Prim 的邻接表思路做对比 —— 这里通常 Prim + 堆更快。

04 / 常见坑

i.
忘记在 N − 1 条边处提前停。
一旦收到 N − 1 条边,生成树就完成了 —— 继续扫只会做无谓的 find/union。 更糟的是,在「边代价并非纯加性」的变种(预算约束、特殊 tie-break)中, 多扫的这些步可能悄悄给出错误答案。请提前 break。
ii.
并查集没有用路径压缩。
Kruskal 的复杂度由排序的 O(E log E) 主导 —— 前提是每次 find / union 接近常数。 若不开路径压缩(或按秩合并),一条长链上的 find 就退化到 O(N), 整个 Kruskal 跌到 O(E · N)。DSU 的这些优化不是锦上添花,是骨架。
iii.
把 MST 和最短路径搞混。
两者都是带「最小」的图算法,但优化的目标不同。 MST 最小化整棵生成树的总权重;最短路径最小化从某点到另一点的路径权重。 MST 上连接两点的边,通常不是这两点之间的最短路径。问题不同,不变量不同,算法也不同。

05 / 去 LeetCode 上练习

四道题。前两道是 Kruskal 的标准练手题。连接所有点的最小费用是稠密图场景 —— 正好对比 Kruskal 与 Prim。关键边与伪关键边把 Kruskal 当作子例程使用,算法变成了一种原语。

01Connecting Cities With Minimum Cost— LC 1135中等→02Min Cost to Connect All Points— LC 1584中等→03Optimize Water Distribution in a Village— LC 1168困难→04Find Critical and Pseudo-Critical Edges in MST— LC 1489困难→

— / 什么时候用哪个

Kruskal
图是边列表且已经在用并查集时用 —— 按边权排序后, 每条边只要两端点在不同分量就收下。以边为中心,不需要任何邻接表。
边列表 + 并查集 · LC 1135 · LC 1489
Prim
图给的是邻接表,或者边数接近 N² 的稠密图时用。从任意起点出发, 把它的出边推进最小堆,反复弹出最便宜的、通向未访问节点的边。以点为中心,树从种子开始生长。
邻接表 + 最小堆 · LC 1168 · LC 1584