Borůvka 算法

每一轮让每个连通块选出一条最小出边并同时合并,O(log n) 轮得到最小生成树。

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

核心思想

初始时每个顶点自成一个连通块。每一轮:

  1. 对每个连通块,找出连接它与其它连通块的最小权边(最小出边)。
  2. 把这些边同时加入生成森林,并合并对应的连通块。

重复直到只剩一个连通块。每轮连通块数量至少减半,所以最多 𝑂(log𝑛) 轮。

正确性

每个连通块的最小出边横跨一个割(该块与其余部分),由割性质,它一定属于某棵 MST。不同连通块同时选边互不冲突,因此可以一起加入。

易错点

  • 图不连通时,某一轮没有任何可合并的边,应返回无解。
  • 同一条边可能同时是两个连通块的最小出边,需要避免重复计数。
  • 每一轮都要重新计算每个连通块的最小出边。
  • 𝑛=1 时答案是 0,循环不会进入。

与其他 MST 算法的取舍

  • Borůvka 不需要排序,轮数 𝑂(log𝑛),天然适合并行和分布式场景。
  • Kruskal 需要排序,代码更短,适合稀疏图。
  • Prim 从点扩展,适合稠密图。
  • 三者都基于割性质,总权值相同;MST 不唯一时可能得到不同的树。

常见用途

  • 隐式完全图:边不显式给出时,每轮用数据结构为每个连通块找最小出边。典型是 Rectilinear MST 和 XOR-MST。
  • 最小生成森林:不要求最终连通,所有轮结束后每个连通块各有一棵 MST。
  • 并行 / 分布式 MST:每一轮各连通块独立选边,天然可并行。
源码位置