算法刷题系列（四十）：最小生成树——用最低代价连接所有顶点

算法刷题系列（四十）：最小生成树——用最低代价连接所有顶点

把若干城市、设备或网络节点连成一个整体，通常不需要保留所有候选连接。若连接是无向的、带有代价，并且要求任意两点最终可达且总成本最低，我们要找的是最小生成树（MST）。

生成树必须包含全部顶点、连通且无环。对于 V 个顶点，它恰好有 V - 1 条边。本文用 Kruskal 算法：从便宜的边开始考虑，只有在它连接两个不同连通分量时才选入。

问题示例

顶点为 0..3，候选边为 (0,1,1)、(1,2,2)、(0,2,4)、(2,3,3)。按权重排序后依次选前三条中不会成环的边，得到总成本 1 + 2 + 3 = 6。权重为 4 的边不必再选，因为 0 与 2 已经连通。

并查集与贪心过程

并查集维护当前已选边形成的连通分量。find(x) 找到分量代表，union(a,b) 合并两个不同分量。路径压缩和按秩（或大小）合并让操作的摊还成本接近常数。

1. 将边按权重从小到大排序。
2. 逐边检查两端：若代表不同，加入答案并合并；否则跳过以避免环。
3. 已选 V - 1 条边时可以提前结束。

正确性直觉：考虑排序中当前最轻、且连接两个不同分量的边。若某棵最优生成树没有这条边，把它加入会形成一个环；环上必有另一条连接这两个分量的边，其权重不小于当前边。用当前边替换它不会增加成本。因此每一步贪心选择都能保留某棵最优解。最终若合并次数达到 V - 1，得到的无环连通图就是 MST。

Java 实现

import java.util.Arrays;

public class Main {
    static class Edge {
        int from;
        int to;
        long weight;
        Edge(int from, int to, long weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    static class UnionFind {
        int[] parent;
        int[] size;
        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
        boolean union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return false;
            if (size[ra] < size[rb]) {
                int temp = ra; ra = rb; rb = temp;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
            return true;
        }
    }

    static Long minimumSpanningTreeCost(int n, Edge[] edges) {
        if (n < 0 || edges == null) throw new IllegalArgumentException();
        if (n == 0) return 0L;
        for (Edge e : edges) {
            if (e == null || e.from < 0 || e.from >= n || e.to < 0 || e.to >= n)
                throw new IllegalArgumentException("invalid edge endpoint");
        }
        Arrays.sort(edges, (a, b) -> Long.compare(a.weight, b.weight));
        UnionFind uf = new UnionFind(n);
        long cost = 0;
        int chosen = 0;
        for (Edge e : edges) {
            if (uf.union(e.from, e.to)) {
                cost += e.weight;
                if (++chosen == n - 1) return cost;
            }
        }
        return n == 1 ? 0L : null; // null 表示图不连通
    }

    public static void main(String[] args) {
        Edge[] edges = {
            new Edge(0, 1, 1), new Edge(1, 2, 2),
            new Edge(0, 2, 4), new Edge(2, 3, 3)
        };
        System.out.println(minimumSpanningTreeCost(4, edges)); // 6
    }
}

Python 实现

from typing import Optional

def minimum_spanning_tree_cost(n: int, edges: list[tuple[int, int, int]]) -> Optional[int]:
    if n < 0 or edges is None:
        raise ValueError("invalid input")
    if n == 0:
        return 0
    for u, v, _ in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("edge endpoint out of range")

    parent = list(range(n))
    size = [1] * n

    def find(x: int) -> int:
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    cost = chosen = 0
    for u, v, weight in sorted(edges, key=lambda edge: edge[2]):
        ru, rv = find(u), find(v)
        if ru == rv:
            continue
        if size[ru] < size[rv]:
            ru, rv = rv, ru
        parent[rv] = ru
        size[ru] += size[rv]
        cost += weight
        chosen += 1
        if chosen == n - 1:
            return cost
    return 0 if n == 1 else None

assert minimum_spanning_tree_cost(4, [(0, 1, 1), (1, 2, 2), (0, 2, 4), (2, 3, 3)]) == 6
assert minimum_spanning_tree_cost(1, []) == 0
assert minimum_spanning_tree_cost(3, [(0, 1, 5)]) is None
assert minimum_spanning_tree_cost(2, [(0, 1, -1)]) == -1

复杂度、边界与误区

排序耗时 O(E log E)，并查集操作总计近似 O(E α(V))，额外空间为 O(V)（不计边数组）。图不连通时不存在生成树，代码约定返回 null（Python 为 None）；单顶点图的成本为 0。边权可以为负数，Kruskal 仍然成立；自环会因两端代表相同而被忽略，重边也无需特殊处理。不要用 -1 当作无解标记，因为合法的最小生成树成本也可能是 -1。成本累计可能超出 32 位整数，因此使用 long。

常见错误是把所有边都选入、在两个已经连通的点之间加边，或把“最小生成树”误当成“从指定源点到每个点的最短路树”。前者会产生环，后者优化目标不同。若图非常稠密且以邻接矩阵存储，也可考虑 Prim；稀疏边列表通常适合 Kruskal。

小结

Kruskal 的核心是按权重排序，并用并查集判断“这条边是否连接了两个不同分量”。拒绝成环边、直到选满 V - 1 条，就以可证明的贪心策略获得最低连接成本。