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$。因此至多 $\lceil {\log }_{2}n\rceil$ 轮，这个界与边权随机性无关。

朴素实现每轮扫描 $m$ 条原边，用 DSU 根识别内部边并更新两端分量的 best edge，总时间 $O(m\log n)$ 再加近线性的并查集开销。断开图对每个原连通分量独立减半，最终输出最小生成森林；孤立点没有候选边。

收缩实现不变量 ​

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

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

Borůvka 每轮让每个连通分量选择最轻出边，这是贪心算法公理库贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。的安全边选择：cut property 保证这些边可同时包含在某棵最小生成树中。分量合并使轮数对数下降。

与 Prim、Kruskal 对照 ​

Prim 从一个连通块逐边扩展，Kruskal 全局按边权排序，Borůvka 为所有分量并行选边并收缩。三者都依赖 cut property，却有不同的数据访问、并行方式与中间状态；不能把 Borůvka 的轮减半界套到另外两种流程。