Borůvka 算法

Borůvka 不是从某一个顶点向外长树，而是让当前森林的每个分量同时寻找最便宜的对外连接。每个非孤立分量都必须与至少另一个分量合并，所以超级顶点数按轮成倍缩小；统一平局规则下的割性质与重复候选处理，使实际接受的森林能够扩充为某棵最小生成树。

一轮状态追踪 ​

设轮初分量为 $A=\{1,2\},B=\{3\},C=\{4,5\}$，跨边最小权分别为 $w(AB)=2,w(AC)=5,w(BC)=3$。A 与 B 都选择 AB，C 选择 BC。去重后依次接受 AB、BC，三个旧分量在这一轮合成一个。

候选可以共享端点，但上述统一平局规则保证去重后没有环。若允许不同分量各自任意打破平局，等权三角形可能让三个顶点各选下一条边而选出整圈，此时还需一个经证明安全的去环方案；本页采用统一边序，直接避免这项额外义务。

轮数与总工作 ​

令某个原连通分量在轮初还含 $c>1$ 个超级顶点。每个超级顶点都有出边并至少选一条，所以候选边图的每个新连通块含至少两个旧分量；轮末超级顶点数至多 $c/2$。因此 $n\ge 1$ 时至多 $\lceil {\log }_{2}n\rceil$ 轮，这个界与边权随机性无关。

一种明确的实现先冻结本轮的分量标签，再扫描 $m$ 条原边。轮内尚未 union 时，父指针森林固定；对全部 $n$ 个顶点做完全路径压缩，可在 $O(n)$ 总时间取得根标签：不直接连根的节点第一次作为查找路径内部节点被访问后，就被压成根的孩子，其余每次查询只付常数收尾成本。之后每条边只查两次数组标签，每轮为 $O(n+m)$。

收集完候选后才执行 union。有出边的活动分量逐轮至少减半，全部轮次的候选记录数为 $O(n)$，这些合并的总成本为 $O(n\alpha (n))$。连同初始化，总时间为 $O((n+m)\log (n+1))$，辅助空间为 $O(n)$；连通且 $n\ge 2$ 时可写为 $O(m\log n)$。这里的线性扫描来自冻结标签与分阶段处理，而不是把一般的单次 DSU 查找当作最坏常数。断开图最终输出最小生成森林；孤立点没有候选边，空图直接结束。

收缩实现不变量 ​

扫描边时应以轮初根为分量身份收集候选，再统一执行 union。若边扫描到一半就合并，后半轮的“每个分量最轻边”会混用两个不同阶段的分量划分，安全性与减半分析都不再对应同一轮。

收缩后，旧内部边可删除；同一对超级顶点之间的平行边只需保留最轻者供 MST 选择。若保留原边列表重复扫描也仍正确，只是工作量较大。候选记录要保存原始端点，才能把超级顶点间选择还原为输出森林边。

与 Prim、Kruskal 对照 ​

Prim 从一个连通块逐边扩展，Kruskal 全局按边权排序，Borůvka 为所有分量并行选边并收缩。三者都用割性质证明贪心选择理路贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。的安全性；Borůvka 的全分量扫描便于并行处理，轮末收缩则逐步减小后续问题的规模。