Boruvka算法计算器

伪代码

每个连通分量各自选出自己最便宜的出边，然后所有这些选择被一次性应用。它以「轮」而非「单步」推进，这正是它可以并行化的根本原因。

Boruvka(图):
    对每个结点执行 建立集合(v)
    mst = []

    当剩余分量多于一个时:
        最便宜 = {} // 按分量记录
        对每条边 (u, v, w):
            a = 查找(u); b = 查找(v)
            若 a == b: 跳过            // 分量内部边
            若 w < 最便宜[a]: 最便宜[a] = (u,v,w)
            若 w < 最便宜[b]: 最便宜[b] = (u,v,w)

        对 最便宜 中的每条边 e:
            若 查找(e.u) != 查找(e.v):  // 可能已被合并
                合并(e.u, e.v); mst.追加(e)

第二个循环里的那道守卫是必需的，而不是出于谨慎才加的。两个分量常常会从各自一端选中同一条边，若不加判断就应用两次，便会重复加入。正确性还要求边权互不相同，或者有一条一致的打破并列的规则，例如比较边的编号：若没有这样的规则，多个分量可能各自选中一条权重相同但不同的边，合起来恰好构成一个环。

分步示例演算

在与 Prim 和 Kruskal 完全相同的图上构造最小生成树，以便三者可以直接对照。

示例图: 无向边 A-B (2)、A-C (3)、B-C (1)、C-D (4) 和 B-D (7)。

1. 起始状态. 每个结点各自构成一个分量：{A}、{B}、{C}、{D}。因此每条边对它的两个端点而言都是出边。
2. 各分量分别选边. 分量 A 在权重 2 的 A-B 与权重 3 的 A-C 之间选择 A-B。分量 B 在 A-B (2)、B-C (1) 和 B-D (7) 之间选择 B-C。分量 C 在 A-C (3)、B-C (1) 和 C-D (4) 之间选择 B-C。分量 D 在 C-D (4) 与 B-D (7) 之间选择 C-D。
3. 留意这处重复. B 与 C 从各自一端提名了同一条边 B-C。第二个循环里的守卫只让它被应用一次，这正是那道检查存在的意义。
4. 一次性应用全部选择. 加入 A-B、B-C 和 C-D 后，一轮之内所有结点就合并成了一个分量。四个结点对应三条边，生成树已经完成。
5. 循环结束. 只剩下一个分量，因此不会进入第二轮。

最小生成树由 A-B、B-C 和 C-D 构成，总权重为 2 + 1 + 4 = 7，与 Prim 和 Kruskal 得到的是同一棵树。Boruvka 只用一轮就完成，而不是三个先后相继的步骤，这正是它的要点：每一轮至少把分量数减半，因为每个分量都会与至少一个其他分量合并，所以永远不需要超过 O(log V) 轮。在这个四结点的例子里，一轮便已足够。

复杂度及其来源

时间: O(E log V) · 空间: O(V + E)

每一轮以 O(E) 扫过全部边，为每个分量找出最便宜的出边。在一轮之内每个分量都会与至少一个其他分量合并，因此分量数至少减半，这把轮数限制在以 2 为底 V 的对数以内。两者相乘得到 O(E log V)，与 Prim 和 Kruskal 相同。它真正与众不同之处在于：在同一轮内每个分量彼此独立地工作，因此这次扫描可以直接并行化，这也是 Boruvka 成为 GPU 与分布式最小生成树实现基础的原因，而 Prim 与 Kruskal 天生是串行的。混合算法会先跑几轮 Boruvka 把图缩小，再切换到 Prim 收尾。

何时使用博鲁夫卡算法，何时不宜

三种经典的最小生成树算法复杂度都是 O(E log V)，区别在于结构。

常见陷阱

• 不处理权重并列的情况. 权重相同时，不同分量可能各自选中不同的边，而这些边合起来正好构成一个环，结果就不再是一棵树。请用一致的方式打破并列，例如按边的编号比较，使所有分量都依据同一套顺序。若所有边权互不相同，这个问题自然就不存在。
• 把同一条边加入两次. 两个分量经常会从相对的两端提名同一条边。如果在应用时不检查两个端点是否仍属于不同分量，这条边就会被加入两次，边数也会超过 V - 1。
• 在扫描边的过程中重复计算分量. 若不做路径压缩就反复调用查找，每一轮的代价会远高于 O(E)。请使用带路径压缩与按秩合并的并查集，与在 Kruskal 中的做法完全一致。
• 以为它要求图必须连通. 与 Kruskal 一样，Boruvka 天然支持非连通输入，并返回一片最小生成森林。但此时循环条件必须改成「没有任何分量还有出边」，而不是「只剩一个分量」，否则它不会终止。
• 忽视它其实早于另外两者. Boruvka 于 1926 年为规划摩拉维亚的一张电网而发表，是已知最早的最小生成树算法，早于 Prim 也早于 Kruskal。它常常被放在最后讲授，这掩盖了并行形式其实最先出现这一事实。

常见问题

Boruvka 算法是怎样工作的？

每个分量同时选出从自己出发的最便宜的边，所有被选中的边一次性加入，从而合并分量。如此反复，直到只剩一个分量为止。由于每轮中每个分量都会与至少一个其他分量合并，分量数每次至少减半，因此只需要 O(log V) 轮。

Boruvka 算法的时间复杂度是多少？

O(E log V)。每一轮扫过全部 E 条边，为每个分量找出最便宜的出边；由于分量数每轮减半，至多进行 log V 轮。这在渐进意义上与 Prim 和 Kruskal 相同。

为什么 Boruvka 算法适合并行计算？

因为在同一轮内，每个分量各自独立地确定自己最便宜的出边，既没有共享状态，也没有顺序要求。这可以直接映射到 GPU 和分布式集群上。Prim 与 Kruskal 则天生串行：两者都依赖于紧接其前做出的那一个全局决策。

为什么要求边权互不相同？

权重并列时，不同分量可能选中代价相同但彼此不同的边，它们合起来构成一个环，结果就不是树。任何一致的打破并列的规则，例如权重相同时比较边的编号，都能恢复正确性。边权互不相同还会使最小生成树本身唯一。

Boruvka、Prim 和 Kruskal 有什么区别？

三者都能以 O(E log V) 给出最小生成树。Prim 用优先队列从一个起始结点生长出一棵树。Kruskal 把所有边排序后加入不成环的边。Boruvka 则让每个分量在并行的轮次中各自选出最便宜的出边，是三者中唯一天然可并行的。