Borůvka 算法 | Codeboy's Blog

算法与安全性

为构造最小生成树，初始令每个顶点自成分量。每轮扫描跨分量边，为每个非孤立分量选择一条最轻出边，再用并查集接受连接不同当前根的候选。

对轮初分量 (C)，其最轻出边 (e) 跨割 ((C,V\setminus C))。取一棵不含 (e) 的 MST，加入 (e) 形成环；环上另有一条跨该割的边 (f)，且 (w(e)\le w(f))。以 (e) 替换 (f) 不增总权，所以 (e) 可属于某棵 MST。

多个分量同时选择时，可按某个顺序应用交换论证。候选边若在此前合并后已经形成环，DSU 会跳过它；相同权重时任一最轻出边都安全，但最终 MST 可能不唯一。

设轮初分量为 (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 选择。若保留原边列表重复扫描也仍正确，只是工作量较大。候选记录要保存原始端点，才能把超级顶点间选择还原为输出森林边。

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

参考资料