Kruskal 算法

把边按权值排序,用并查集依次加入不成环的边,最终得到最小生成树。

时间 O(m log m),空间 O(n + m) · 标签 图论 / 最小生成树 / 并查集 / 贪心

核心思想

把所有边按权值从小到大排序,依次尝试加入当前的生成森林:

  • 如果一条边的两个端点还不连通,就选它,并把两个连通块合并。
  • 如果两个端点已经连通,加入会形成环,跳过。

“是否连通”和“合并”用并查集维护。排序后最多扫描一遍边表。

正确性

  • 当前并查集的每个连通块是一个点集。取其中一个块与其余部分构成割,排序后第一条连接该块与外部的边,就是横跨这个割的最小边;由割性质,它是安全的。
  • 若一条边两端已经连通,加入会成环;环上其余边都不比它重,由环性质,这条边可以跳过。

这两个性质都来自最小生成树本身,Kruskal 只是按边权顺序执行它们。

易错点

  • 图不连通时没有 MST:最后检查选中的边数是否为 𝑛−1。
  • 选满 𝑛−1 条边后可以提前退出,不必扫描剩余边。
  • 𝑛=1 时答案是 0,不需要任何边。

与 Prim 的取舍

  • Kruskal 从边扩展,需要排序,适合稀疏图。
  • Prim 从点扩展,适合稠密图;邻接矩阵可以做到 𝑂(𝑛2)。
  • 两者都基于割性质,总权值相同;MST 不唯一时可能得到不同的树。

变式

  • 最小生成森林:不要求最终连通,把所有能合并的边都选上即可。
  • 虚拟源点:把“自建”方案连到一个虚拟点,再跑 Kruskal。
  • 次小生成树:先求 MST,再枚举非树边替换路径上的最大边。
  • 瓶颈生成树:使最大边权最小;MST 就是一棵瓶颈生成树。
源码位置