专题进阶 · 图算法推荐总顺序 · 第 79 / 148 课

按边权扫描,用并查集跳过成环边并识别不连通输入。

先学会这些,再进入本课 最小生成树 并查集
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

KruskalKruskal

按边权排序,使用并查集跳过成环边,逐步构建最小生成树。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

按边权扫描,用并查集跳过成环边并识别不连通输入。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 初始空边集为森林。
  2. 只连接不同分量,始终无环。
  3. 每次安全边可包含在某棵最优树中,选满 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 · 复现与理解

三角形三条边都是 1,会选几条?

需要一点提示

第三条是否成环?

查看解析与答案

选两条,总重 2;具体哪两条依平局顺序。

练习 2 · 边界与辨析

为什么不能选轻自环?

需要一点提示

自环连接了新分量吗?

查看解析与答案

没有,且本身成环,不属于生成树。

练习 3 · 变式与迁移

怎样得到最小生成森林?

需要一点提示

取消全图必须连通的返回限制。

查看解析与答案

保留已选安全边并返回总重、边集与分量数,明确结果不一定是一棵树。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。