Kruskal 算法
把边按权值排序,用并查集依次加入不成环的边,最终得到最小生成树。时间 O(m log m),空间 O(n + m) · 标签 图论 / 最小生成树 / 并查集 / 贪心
核心思想
把所有边按权值从小到大排序,依次尝试加入当前的生成森林:
- 如果一条边的两个端点还不连通,就选它,并把两个连通块合并。
- 如果两个端点已经连通,加入会形成环,跳过。
“是否连通”和“合并”用并查集维护。排序后最多扫描一遍边表。
正确性
- 当前并查集的每个连通块是一个点集。取其中一个块与其余部分构成割,排序后第一条连接该块与外部的边,就是横跨这个割的最小边;由割性质,它是安全的。
- 若一条边两端已经连通,加入会成环;环上其余边都不比它重,由环性质,这条边可以跳过。
这两个性质都来自最小生成树本身,Kruskal 只是按边权顺序执行它们。
易错点
- 图不连通时没有 MST:最后检查选中的边数是否为 。
- 选满 条边后可以提前退出,不必扫描剩余边。
- 时答案是 0,不需要任何边。
与 Prim 的取舍
- Kruskal 从边扩展,需要排序,适合稀疏图。
- Prim 从点扩展,适合稠密图;邻接矩阵可以做到 。
- 两者都基于割性质,总权值相同;MST 不唯一时可能得到不同的树。
变式
- 最小生成森林:不要求最终连通,把所有能合并的边都选上即可。
- 虚拟源点:把“自建”方案连到一个虚拟点,再跑 Kruskal。
- 次小生成树:先求 MST,再枚举非树边替换路径上的最大边。
- 瓶颈生成树:使最大边权最小;MST 就是一棵瓶颈生成树。