Borůvka 最小生成树算法

Borůvka 在每一轮中，让每个连通分量选择一条最小权外连边，再合并这些分量。与 Prim 扩展一棵树、Kruskal 按全局边权排序不同，它同时扩展多个分量。

选择与合并

初始时，每个顶点各自构成一个分量。每轮扫描全部边，为每个分量记录最小外连边；随后重新检查候选边两端是否已合并，仅在仍属不同分量时加入。

相同边权可能使多个分量的候选形成环，不能直接把全部候选边加入答案。例如等权三角形的三个顶点可能各选一条不同的边。实现中为边固定编号，按 (权值, 编号) 统一打破平局，并用并查集再次检查，保证不重复加边、不成环。

实现

边表每项为 (u, v, weight)，无向边只存一次。以下 DSU 定义与 Kruskal 实现相同。

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

def boruvka(n, edges):
    dsu = DSU(n)
    components = n
    total, tree = 0, []
    while components > 1:
        cheapest = {}
        for i, (u, v, weight) in enumerate(edges):
            a, b = dsu.find(u), dsu.find(v)
            if a == b:
                continue
            for root in (a, b):
                old = cheapest.get(root)
                if old is None or (weight, i) < (edges[old][2], old):
                    cheapest[root] = i
        merged = 0
        for i in cheapest.values():
            u, v, weight = edges[i]
            if dsu.union(u, v):
                total += weight
                tree.append((u, v, weight))
                components -= 1
                merged += 1
        if merged == 0:
            return None
    return total, tree

正确性与复杂度

每条候选边都是某个分量割上的最小边。统一打破平局后，可以把边看成按微小扰动得到互异权值，每条候选都属于该顺序确定的最小生成树；扰动只在原权值相同时影响选择，不改变原问题的最优总权值。

连通图中，每个分量都有外连边，因此合并后的每个分量至少包含两个旧分量，分量数每轮至少减半，共 $O(\log n)$ 轮。

每轮扫描 $m$ 条边。把分量查询视为常数时，通常将扫描复杂度记为 $O(m\log n)$；上面直接调用并查集的实现保守计为 $O((n+m\log n)\alpha(n))$。辅助空间为 $O(n)$，不含输入边表和输出。非连通图在无法继续合并时返回 None，不会无限循环。