01先把问题说具体
从一个城市开始逐步铺网,怎样只考虑当前已联网区域与外界之间的边?
02一步步得到方法
与 Kruskal 的森林视角对照
Prim 始终生长一棵树。起点加入后,把连接外部节点的边放入小根堆,每次取最轻跨边,将新节点加入树,再把它的出边加入候选。
边堆里会残留终点已经在树内的记录。这些边此时不再跨越割,必须跳过;不能因为是堆顶最轻就盲目接受。
为什么不需要累计源点距离
优先级是单条跨边的权重 w,而不是 dist[u]+w。Prim 最小化总铺网成本,Dijkstra 最小化源点路径代价;两者都用堆,却维护不同不变量。
当前树节点与其余节点构成一个割,选择其最轻跨边由割性质保证安全。图不连通时,堆会提前耗尽,无法覆盖所有节点。
每次选择当前树与外部之间的边
Prim 维护一个已经连通的节点集合,只从跨出这个集合的边中选最小边。它与 Kruskal 全图按边排序不同,也与 Dijkstra 选择最小累计距离不同。
惰性堆可能含两端都已进入树的旧边,出堆时要跳过。若误用从起点的累计距离作为键,就会把目标悄悄改成最短路径树。
03把一个小例子完全算清楚
边 0–1:2、0–2:3、1–2:1、2–3:4,从 0 出发。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 树 {0} | 候选 0–1:2、0–2:3 | 选权重 2 |
| 树 {0,1} | 新增 1–2:1 | 选 1,而非按源点累计 3 比较 |
| 树 {0,1,2} | 旧 0–2:3 已过期 | 跳过 |
| 加入 3 | 选 2–3:4,总重 7 | 完成 |
窄屏可左右滑动表格,阅读完整计算与理由。
跨边代价与路径代价必须分开理解。
04为什么这个方法成立
- 已接受边始终连接一个新节点,因此维持树且无环。
- 堆中保留所有从已选树通向外部的候选边。
- 跳过内部边后弹出的最轻边就是最轻跨割边,逐轮安全。
05把推导翻译成代码
Python · 可独立运行的教学实现
import heapq
def prim(n, edges):
if n == 0:
return 0
adj = [[] for _ in range(n)]
for u,v,w in edges:
adj[u].append((w,v)); adj[v].append((w,u))
heap, seen, total = [(0,0)], set(), 0
while heap:
weight,u = heapq.heappop(heap)
if u in seen:
continue
seen.add(u); total += weight
for w,v in adj[u]:
if v not in seen:
heapq.heappush(heap,(w,v))
return total if len(seen)==n else None逐个理解关键决定
[(0,0)]- 起点用虚拟零成本入口,后续真实边权才累入成本。
(w,v)- 键是边权,不是 total+w 或源点路径长度。
06时间、空间与实现范围
本惰性边堆版本 O(E log(E+1)+V),堆最坏 O(E),邻接表 O(V+E)。
稠密图可用 O(V²) 扫描版,带索引的堆版也有不同复杂度;应对应实际实现。
07改变条件,检查哪里会出错
发现节点时立刻 seen
可能在更便宜跨边出现前锁定它;本版本在最轻候选弹出时接纳。
只运行一次就覆盖断开的图
从一个起点只能扩展其连通分量;要返回森林需遍历其他未访问起点。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
允许负权吗?
需要一点提示
割性质是否要求非负?
查看解析与答案
允许;虚拟起点为 0 不限制后续负边加入。
Prim 从不同起点开始总重会变吗?
需要一点提示
最小树是否唯一?
查看解析与答案
在连通图上最优总重相同,等权时选出的边集可以不同。
不连通图怎样扩展为森林?
需要一点提示
为未访问分量重新启动。
查看解析与答案
外层遍历所有未访问节点,每个分量独立运行 Prim,分别记录生成树。