最小生成树

在一张连通、带权、无向图中，最小生成树是连接所有顶点而不成环、并使所选边权总和最小的生成树。如果图有 $n$ 个顶点，任何生成树都恰有 $n - 1$ 条边；优化的是这些边的权重之和，不是边数。若原图不连通，则不存在覆盖全部顶点的生成树，可以分别求每个连通分量的最小生成树，合起来称最小生成森林。

一个四点网络

设边及权重为 $A B : 1$ 、 $B C : 2$ 、 $A C : 3$ 、 $C D : 4$ 、 $B D : 5$ 。按权重从小到大考虑：先取 $A B$ ，再取 $B C$ ；此时 $A, B, C$ 已连通， $A C$ 会与前两条边构成环，故跳过；再取 $C D$ 接入 $D$ 。所得树权重为 $1 + 2 + 4 = 7$ 。若把 $B C$ 换成 $A C$ ，仍得到一棵树，权重却变为 $8$ 。

上述过程是Kruskal 算法。它始终保持已经选择的边是一片森林；每次只接入两个不同连通分量之间的最轻候选边，所以不会成环。取满 $n - 1$ 条边即停止。

跨割的轻边

把顶点集分成非空的 $S$ 与 $V ∖ S$ ，横跨两侧的边叫这个割上的边。任取割上一条权重最小的边 $e$ ，至少存在一棵最小生成树含有 $e$ 。证明：若某棵最小生成树 $T$ 不含 $e$ ，添上 $e$ 会形成一个环；环必须还有另一条跨同一割的边 $f$ 。删去 $f$ 后仍是生成树，且 $w (e) \leq w (f)$ ，总权重不会增加，因而仍最小。权重并列时最小生成树可能不唯一，结论只保证可以选到一棵含 $e$ 的。

Kruskal 每次添加的边连接当前森林的两个分量，并是该分量跨割边中的最轻者：若有更轻的跨割边，它会更早被扫描，当时两端也尚未在同一分量，理应被加入。故上面的换边论证可以在每一步保留此前所选边，直到形成最小生成树。这里的“最轻”必须比较当前相关割上的边；单独挑全图最短的 $n - 1$ 条边可能形成环或漏掉顶点。

可复算的 Python 实现

输入 n 为编号 0 到 n-1 的顶点数，edges 为 (权重, 端点一, 端点二) 三元组。函数不改写输入，返回 (总权重, 选中边)；若不连通则抛出异常。并查集记录当前森林的分量。

Python 3

def minimum_spanning_tree(n, edges):
    if n < 1:
        raise ValueError("n must be positive")
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        while not (parent[x] == x):
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return False
        if rank[a] < rank[b]:
            a, b = b, a
        parent[b] = a
        if rank[a] == rank[b]:
            rank[a] += 1
        return True

    chosen = []
    total = 0
    for weight, u, v in sorted(edges):
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("vertex outside 0..n-1")
        if union(u, v):
            chosen.append((weight, u, v))
            total += weight
            if len(chosen) == n - 1:
                break
    if len(chosen) == n - 1:
        return total, chosen
    raise ValueError("graph is disconnected")

sample = [(1, 0, 1), (2, 1, 2), (3, 0, 2),
          (4, 2, 3), (5, 1, 3)]
print(minimum_spanning_tree(4, sample))
# (7, [(1, 0, 1), (2, 1, 2), (4, 2, 3)])

排序耗时 $O (| E | \log | E |)$ ；路径压缩与按秩合并使并查集操作的总成本更低，整体由排序主导。空间需要 $O (| V | + | E |)$ （排序后的边及并查集）。边权允许为负值，因为证明只比较权重，不要求非负；这与某些最短路径算法的非负条件不同。

从割重新核对算例

不运行代码，也能看出前面四点网络的答案。把 $A$ 与其余三点分开，跨割边是 $A B : 1$ 和 $A C : 3$ ，前者是唯一最轻边；把 $D$ 单独分开，跨割边是 $C D : 4$ 和 $B D : 5$ ，前者同样唯一最轻。为了连接 ${A, B}$ 与 ${C, D}$ ，跨割边 $B C : 2$ 又比 $A C : 3$ 、 $B D : 5$ 轻。这三条必选边恰好构成树，给出了不依赖程序输出的核验。如果把 $A C$ 的权重也改成 2，第二步可以有不同选择；不同的最小生成树都可能总权重为 7，算法的排序并列次序只影响选出哪一棵。

最小生成树与最短路径不能混作一题。前者最小化所有选中边的总和，例如要用尽量少的电缆把所有站点连接起来；后者最小化指定起点到终点沿途的权重和。在本例从 $A$ 到 $C$ 的最短路是 $A - B - C$ ，长度 3，与直连边 $A C : 3$ 并列；最小生成树选用 $A B, B C, C D$ 是为覆盖四点服务，不是保证树中任意两点间的距离都与原图一样短。

参考资料