01先把问题说具体
全图边已给出,怎样每次挑便宜边,又不把闭环的多余线路也买下来?
02一步步得到方法
已选边始终是一片森林
按边权从小到大扫描。若 u、v 的代表不同,这条边连接两个分量,加入不会成环,于是合并;若代表相同,二者已有路径,再加边必成环,应跳过。
不要把排序后最小的 V−1 条直接拿走,它们可能全部集中在某个局部环里。并查集负责检查是否真的把森林向更少分量推进。
排序与割性质连接起来
考虑当前 u 所在分量与其余节点组成的割。若有更轻的跨割边,它早已被扫描,并会连接不同分量,不可能被无故丢掉。因此当前可用的最轻边满足安全选择条件。
每加入一条边,分量数减少一。成功选满 V−1 条就连通;扫描结束仍不足,说明图不连通,本接口返回 None。
按边排序后只问是否连接不同分量
并查集表示当前已选边形成的森林。候选边两端若同根,加入它会闭合一条环;若不同根,它把两棵树合成一棵,能够增加连接范围。
安全性来自割性质:当这条最便宜可用边跨过当前分量边界时,可通过交换论证找到包含它的某棵最优生成树。并查集只是高效检测环,最优性的来源不是数据结构本身。
03把一个小例子完全算清楚
边 (0,1,1)、(1,2,2)、(0,2,3)、(2,3,4)。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 选 0–1 | 分量 {0,1},{2},{3},成本 1 | 连接不同根 |
| 选 1–2 | 分量 {0,1,2},{3},成本 3 | 继续合并 |
| 跳过 0–2 | 两个端点已连通 | 否则成环 |
| 选 2–3 | 成本 7,3 条边 | 完成生成树 |
窄屏可左右滑动表格,阅读完整计算与理由。
边选择的顺序由权重决定,合法性由连通分量决定。
04为什么这个方法成立
- 初始空边集为森林。
- 只连接不同分量,始终无环。
- 每次安全边可包含在某棵最优树中,选满 V−1 条后得到最小生成树。
05把推导翻译成代码
Python · 可独立运行的教学实现
def kruskal(n, edges):
parent, size = list(range(n)), [1]*n
def find(x):
while x != parent[x]:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total, chosen = 0, []
for u,v,w in sorted(edges, key=lambda e:e[2]):
a,b = find(u),find(v)
if a == b:
continue
if size[a] < size[b]:
a,b = b,a
parent[b] = a; size[a] += size[b]
total += w; chosen.append((u,v,w))
return (total,chosen) if len(chosen)==max(0,n-1) else None逐个理解关键决定
find(u),find(v)- 比较根,不是只比较 parent[u] 和 parent[v] 的即时值。
size[a] += size[b]- 按大小合并并维护大小,与路径压缩共同控制并查集开销。
06时间、空间与实现范围
边排序 O(E log E) 主导,合并查询摊还 O(E α(V)),空间 O(V+E) 含排序副本。
稀疏图且边表易获取时很方便;负权、多重边可处理,自环因同根自动跳过。
07改变条件,检查哪里会出错
只看端点是否已被访问
两个已访问节点仍可能属于不同分量;应检查集合代表。
图断开却无条件返回 MST
结束时应检查是否选满 n−1 条边;否则返回的是森林或应报告不连通。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
三角形三条边都是 1,会选几条?
需要一点提示
第三条是否成环?
查看解析与答案
选两条,总重 2;具体哪两条依平局顺序。
为什么不能选轻自环?
需要一点提示
自环连接了新分量吗?
查看解析与答案
没有,且本身成环,不属于生成树。
怎样得到最小生成森林?
需要一点提示
取消全图必须连通的返回限制。
查看解析与答案
保留已选安全边并返回总重、边集与分量数,明确结果不一定是一棵树。