Borůvka 算法
每一轮让每个连通块选出一条最小出边并同时合并,O(log n) 轮得到最小生成树。时间 O(m log n),空间 O(n + m) · 标签 图论 / 最小生成树 / 贪心 / Borůvka
核心思想
初始时每个顶点自成一个连通块。每一轮:
- 对每个连通块,找出连接它与其它连通块的最小权边(最小出边)。
- 把这些边同时加入生成森林,并合并对应的连通块。
重复直到只剩一个连通块。每轮连通块数量至少减半,所以最多 轮。
正确性
每个连通块的最小出边横跨一个割(该块与其余部分),由割性质,它一定属于某棵 MST。不同连通块同时选边互不冲突,因此可以一起加入。
易错点
- 图不连通时,某一轮没有任何可合并的边,应返回无解。
- 同一条边可能同时是两个连通块的最小出边,需要避免重复计数。
- 每一轮都要重新计算每个连通块的最小出边。
- 时答案是 0,循环不会进入。
与其他 MST 算法的取舍
- Borůvka 不需要排序,轮数 ,天然适合并行和分布式场景。
- Kruskal 需要排序,代码更短,适合稀疏图。
- Prim 从点扩展,适合稠密图。
- 三者都基于割性质,总权值相同;MST 不唯一时可能得到不同的树。
常见用途
- 隐式完全图:边不显式给出时,每轮用数据结构为每个连通块找最小出边。典型是 Rectilinear MST 和 XOR-MST。
- 最小生成森林:不要求最终连通,所有轮结束后每个连通块各有一棵 MST。
- 并行 / 分布式 MST:每一轮各连通块独立选边,天然可并行。