最小生成树
01 / 共享的机制
最小生成树是把一张带权无向图所有节点连起来的最便宜方式 ——恰好 N − 1 条边、无环、总权重最小。 两种经典构造方式:Kruskal按边权排序后从小到大走, 用并查集跳过任何会成环的边;Prim从某个节点出发,用最小堆不断把当前树的最便宜出边吸进来。
01 / 一句话本质
生成树从一个种子节点开始,一次吸收一条边长大 —— 每次都取当前树到未访问节点之间最便宜的那条横切边。 用最小堆维护候选的横切边,跑 N − 1 轮就能把整棵树长完。
题目带权无向图上的最小生成树图网格种子0
图有 6 个节点。选定种子,每轮吸收最便宜的横切边,树就长起来。
步
0 / 7
堆
—
树
0 / 6
总权重
0
0 / 7
02 / 模式骨架
# Prim 算法 —— 从种子节点开始生长visited ← {s}pq ← 最小堆 (w, s, v) for (v, w) in neighbors(s)mst ← [ ], total ← 0while pq 非空 且 |visited| < N:(w, u, v) ← pq.pop_min() # 最轻的横切边if v in visited: continue # 已在树中,跳过visited.add(v); mst.append((u, v, w)); total += wfor (x, w') in neighbors(v): # 推入新前沿if x not in visited:pq.push((w', v, x))
03 / 什么时候用这个模式
"从种子节点生成最小生成树"
要把一张带权无向图的所有节点用最便宜的方式连起来,且图是以邻接表形式给出 —— 从任意一个节点出发往外长,正是 Prim 的舒适区: 它需要的就是 {节点 → 邻居} 这种数据结构。
"稠密图(E ≈ N²)"
当边数几乎填满 N × N 矩阵时,Prim 占优:二叉堆实现 O(E log V), 数组 PQ 实现 O(V²);两种都比 Kruskal 把 E ≈ V² 条边从头排序更快。
"电缆 / 管道网络"
连城市、铺光纤、合并集群 —— 凡是「每个节点都连通,总线长最短」的题, 种子-生长的叙事方式刚好对应你实际铺线的过程。
"加一条边保持连通"
题目把生长过程描述为「一次添一条边」并要求每一步都最便宜时, Prim 的「割-吸收」循环比 Kruskal 的「排序-合并」更贴近题意。
04 / 常见坑
i.
把通向已访问节点的边又推回堆里。
每吸收一个节点就要推它的全部出边 —— 但很多邻居已经在树中。 如果在推入前不加
if v not in visited 守卫,堆里就会堆满过期项, 内存和 log 因子双双膨胀。入堆时过滤(便宜)、出堆时再次跳过过期项(也便宜) —— 两者都对,且通常都需要。ii.
把 Prim 和 Dijkstra 搞混。
它们长得几乎一样 —— 图、最小堆、visited 集合、while 循环 —— 但堆中的键完全不同。 Dijkstra 存的是
dist[v]:从源点累加的距离;Prim 存的只是 w: 横切的那条边的权重。混用后,你会在同一张图上算错答案,而且不会有任何报错。iii.
对稀疏图使用邻接矩阵。
经典的数组 PQ Prim 复杂度一律是 O(V²),不管边数 —— E ≈ V² 时很合适,E ≪ V² 时浪费。图稀疏就改用邻接表 + 二叉堆, 复杂度回到 O(E log V);或者用 Kruskal 的边列表 + 并查集,同样的界。
05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。
— / 什么时候用哪个
Kruskal
图是边列表且已经在用并查集时用 —— 按边权排序后, 每条边只要两端点在不同分量就收下。以边为中心,不需要任何邻接表。
边列表 + 并查集 · LC 1135 · LC 1489
Prim
图给的是邻接表,或者边数接近 N² 的稠密图时用。从任意起点出发, 把它的出边推进最小堆,反复弹出最便宜的、通向未访问节点的边。以点为中心,树从种子开始生长。
邻接表 + 最小堆 · LC 1168 · LC 1584