最小生成树

最小生成树（Minimum Spanning Tree, MST）是图论中的经典问题。给定一个连通的无向带权图，最小生成树是一棵包含所有顶点的树，且边的权值之和最小。

基本概念

什么是生成树？

生成树是连通图的一个子图，满足：

1. 包含图中的所有顶点
2. 是一棵树（无环、连通）
3. 边数为 $V - 1$（$V$ 为顶点数）

什么是最小生成树？

在所有可能的生成树中，边的权值之和最小的那棵。

注意：最小生成树可能不唯一，但权值和是唯一的。

应用场景

• 网络设计：铺设通信电缆，连接所有城市且成本最低
• 电路设计：连接所有元件的布线问题
• 聚类分析：基于最小生成树的聚类算法
• 图像处理：图像分割

Prim 算法

Prim 算法是一种贪心算法，从任意一个顶点开始，逐步扩展生成树。

算法思想

1. 从任意顶点出发，将其加入生成树
2. 在所有连接"已加入顶点"和"未加入顶点"的边中，选择权值最小的边
3. 将该边连接的未加入顶点加入生成树
4. 重复步骤 2-3，直到所有顶点都加入

图解示例

初始图：
    A ---4--- B
    |        /|
    8      2  6
    |    /    |
    C --3--- D

执行过程：
1. 从 A 开始，A 加入集合 {A}
2. A 的邻边：A-B(4), A-C(8)，选最小的 A-B
   集合 {A, B}
3. 当前边：A-C(8), B-C(2), B-D(6)，选最小的 B-C
   集合 {A, B, C}
4. 当前边：A-C(8)已无效, B-D(6), C-D(3)，选最小的 C-D
   集合 {A, B, C, D}

最小生成树：A-B(4) + B-C(2) + C-D(3) = 9

朴素实现

时间复杂度 $O(V^2)$，适合稠密图。

/**
 * Prim 算法 - 朴素实现
 * 时间复杂度: O(V²)
 * 空间复杂度: O(V)
 * 
 * @param graph 邻接矩阵表示的图，graph[i][j] 表示边 i-j 的权重
 * @return 最小生成树的权值和
 */
public int prim(int[][] graph) {
    int n = graph.length;
    
    int[] lowCost = new int[n];        // 顶点到生成树的最小距离
    boolean[] inTree = new boolean[n]; // 顶点是否已在生成树中
    
    // 初始化：所有距离设为无穷大
    Arrays.fill(lowCost, Integer.MAX_VALUE);
    
    // 从顶点 0 开始
    lowCost[0] = 0;
    int totalWeight = 0;
    
    for (int i = 0; i < n; i++) {
        // 找到距离生成树最近的未加入顶点
        int u = -1;
        int minCost = Integer.MAX_VALUE;
        
        for (int j = 0; j < n; j++) {
            if (!inTree[j] && lowCost[j] < minCost) {
                minCost = lowCost[j];
                u = j;
            }
        }
        
        if (u == -1) {
            return -1;  // 图不连通
        }
        
        // 将顶点 u 加入生成树
        inTree[u] = true;
        totalWeight += lowCost[u];
        
        // 更新其他顶点到生成树的距离
        for (int v = 0; v < n; v++) {
            if (!inTree[v] && graph[u][v] != 0 && graph[u][v] < lowCost[v]) {
                lowCost[v] = graph[u][v];
            }
        }
    }
    
    return totalWeight;
}

优先队列优化

使用最小堆优化查找最近顶点的过程，时间复杂度 $O(E \log V)$，适合稀疏图。

/**
 * Prim 算法 - 优先队列优化
 * 时间复杂度: O(E log V)
 * 
 * @param n 顶点数
 * @param edges 边列表，每条边为 [u, v, weight]
 * @return 最小生成树的权值和
 */
public int primOptimized(int n, List<int[]> edges) {
    // 构建邻接表
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        adj.get(u).add(new int[]{v, w});
        adj.get(v).add(new int[]{u, w});
    }
    
    boolean[] inTree = new boolean[n];
    // 优先队列：[权重, 顶点]
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    
    // 从顶点 0 开始
    pq.offer(new int[]{0, 0});
    
    int totalWeight = 0;
    int count = 0;
    
    while (!pq.isEmpty() && count < n) {
        int[] curr = pq.poll();
        int weight = curr[0];
        int u = curr[1];
        
        if (inTree[u]) {
            continue;  // 已加入，跳过（惰性删除）
        }
        
        inTree[u] = true;
        totalWeight += weight;
        count++;
        
        // 将所有邻边加入队列
        for (int[] neighbor : adj.get(u)) {
            int v = neighbor[0];
            int w = neighbor[1];
            if (!inTree[v]) {
                pq.offer(new int[]{w, v});
            }
        }
    }
    
    return count == n ? totalWeight : -1;
}

正确性证明

Prim 算法的正确性基于切分定理：

切分定理：将图的顶点集分为两部分（切分），连接两部分的边中，权值最小的边一定属于某棵最小生成树。

证明思路：

1. 设 Prim 算法生成的树为 $T$，最小生成树为 $T^*$
2. 假设 $T \neq T^*$，考虑第一条不在 $T^*$ 中的边 $e$
3. 根据切分定理，$e$ 是连接当前切分的最小边
4. 将 $e$ 加入 $T^*$ 会形成环，环上必有另一条边 $e'$ 连接同样的切分
5. 由于 $e$ 是最小边，$w(e) \leq w(e')$，可以用 $e$ 替换 $e'$
6. 矛盾，故 $T = T^*$

Kruskal 算法

Kruskal 算法按边的权值排序，从小到大选择边，只要不形成环就加入。

算法思想

1. 将所有边按权值从小到大排序
2. 从权值最小的边开始，如果这条边连接的两个顶点不在同一连通分量中，就加入这条边
3. 重复直到选了 $V-1$ 条边

核心工具：并查集

判断两个顶点是否在同一连通分量，以及合并两个连通分量，使用并查集可以高效实现。

/**
 * Kruskal 算法
 * 时间复杂度: O(E log E)，主要是排序的时间
 * 
 * @param n 顶点数
 * @param edges 边列表
 * @return 最小生成树的权值和
 */
public int kruskal(int n, List<int[]> edges) {
    // 按权重排序
    edges.sort((a, b) -> a[2] - b[2]);
    
    UnionFind uf = new UnionFind(n);
    
    int totalWeight = 0;
    int edgeCount = 0;
    
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];
        
        // 如果 u 和 v 不连通，选择这条边
        if (!uf.connected(u, v)) {
            uf.union(u, v);
            totalWeight += weight;
            edgeCount++;
            
            // 已选择 n-1 条边，完成
            if (edgeCount == n - 1) {
                break;
            }
        }
    }
    
    // 检查图是否连通
    return edgeCount == n - 1 ? totalWeight : -1;
}

/**
 * 并查集实现
 */
class UnionFind {
    private int[] parent;
    private int[] rank;
    private int count;
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    
    // 路径压缩查找
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    // 按秩合并
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) {
            return false;  // 已经在同一集合
        }
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        
        count--;
        return true;
    }
    
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    
    public int count() {
        return count;
    }
}

正确性证明

Kruskal 算法的正确性同样基于切分定理：

• 设算法已选边集为 $A$，当前考虑边 $e = (u, v)$
• $A$ 将顶点划分为若干连通分量
• 如果 $u$ 和 $v$ 在不同连通分量，根据切分定理，$e$ 是连接这两个分量的最小边（因为边已排序）
• 因此 $e$ 属于某棵 MST

算法对比

特性	Prim 算法	Kruskal 算法
思路	从顶点扩展	从边选择
时间复杂度	$O(V^2)$ 或 $O(E \log V)$	$O(E \log E)$
适用场景	稠密图	稀疏图
实现复杂度	中等	简单（依赖并查集）
存储结构	邻接矩阵或邻接表	边列表

选择建议

• 边多（稠密图）：使用 Prim 朴素版 $O(V^2)$
• 边少（稀疏图）：使用 Prim 优化版或 Kruskal $O(E \log V)$
• 需要输出具体边：Kruskal 更直观

求最小生成树的边

有时不仅需要求权值和，还需要输出具体选择了哪些边：

/**
 * Kruskal 算法 - 返回最小生成树的边
 */
public List<int[]> kruskalWithEdges(int n, List<int[]> edges) {
    edges.sort((a, b) -> a[2] - b[2]);
    
    UnionFind uf = new UnionFind(n);
    List<int[]> mst = new ArrayList<>();
    
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], weight = edge[2];
        
        if (!uf.connected(u, v)) {
            uf.union(u, v);
            mst.add(new int[]{u, v, weight});
            
            if (mst.size() == n - 1) {
                break;
            }
        }
    }
    
    return mst.size() == n - 1 ? mst : null;
}

进阶应用

次小生成树

有时需要求权值和第二小的生成树。

思路：

1. 先求 MST
2. 对于 MST 中的每条边 $e$，尝试用不在 MST 中的边替换
3. 找到使权值和增加最少的替换方案

/**
 * 求次小生成树
 * 时间复杂度: O(V * E)
 */
public int secondMST(int n, List<int[]> edges) {
    // 先求 MST
    edges.sort((a, b) -> a[2] - b[2]);
    UnionFind uf = new UnionFind(n);
    boolean[] inMST = new boolean[edges.size()];
    
    int mstWeight = 0;
    int edgeCount = 0;
    
    for (int i = 0; i < edges.size(); i++) {
        int[] edge = edges.get(i);
        if (!uf.connected(edge[0], edge[1])) {
            uf.union(edge[0], edge[1]);
            mstWeight += edge[2];
            inMST[i] = true;
            edgeCount++;
            if (edgeCount == n - 1) break;
        }
    }
    
    int secondMin = Integer.MAX_VALUE;
    
    // 尝试删除 MST 中的每条边
    for (int i = 0; i < edges.size(); i++) {
        if (!inMST[i]) continue;
        
        // 重新求不包含该边的 MST
        UnionFind uf2 = new UnionFind(n);
        int weight = 0;
        int count = 0;
        
        for (int j = 0; j < edges.size(); j++) {
            if (i == j) continue;  // 跳过当前边
            
            int[] edge = edges.get(j);
            if (!uf2.connected(edge[0], edge[1])) {
                uf2.union(edge[0], edge[1]);
                weight += edge[2];
                count++;
                if (count == n - 1) break;
            }
        }
        
        if (count == n - 1 && weight > mstWeight) {
            secondMin = Math.min(secondMin, weight);
        }
    }
    
    return secondMin == Integer.MAX_VALUE ? -1 : secondMin;
}

最小生成森林

当图不连通时，求每个连通分量的最小生成树，合起来叫最小生成森林。

Kruskal 算法天然支持这种情况，只需处理完所有边即可：

/**
 * 求最小生成森林
 * 返回每个连通分量的 MST 权值和
 */
public List<Integer> minimumSpanningForest(int n, List<int[]> edges) {
    edges.sort((a, b) -> a[2] - b[2]);
    
    UnionFind uf = new UnionFind(n);
    Map<Integer, Integer> componentWeight = new HashMap<>();
    
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        
        if (!uf.connected(u, v)) {
            int rootU = uf.find(u);
            int rootV = uf.find(v);
            
            int weightU = componentWeight.getOrDefault(rootU, 0);
            int weightV = componentWeight.getOrDefault(rootV, 0);
            
            uf.union(u, v);
            int newRoot = uf.find(u);
            
            componentWeight.put(newRoot, weightU + weightV + w);
            componentWeight.remove(rootU == newRoot ? rootV : rootU);
        }
    }
    
    return new ArrayList<>(componentWeight.values());
}

小结

最小生成树算法的核心要点：

算法	核心思想	时间复杂度	适用场景
Prim	从顶点扩展	$O(V^2)$ 或 $O(E \log V)$	稠密图
Kruskal	按边权选择	$O(E \log E)$	稀疏图

关键数据结构：

• Prim：优先队列（最小堆）
• Kruskal：并查集

证明基础：切分定理

练习

基础：

1. LeetCode 1584：连接所有点的最小费用
2. LeetCode 1135：最低成本连通所有城市

进阶： 3. LeetCode 1168：水资源分配优化 4. LeetCode 1489：找到最小生成树里的关键边和伪关键边 5. LeetCode 1579：保证图完全可遍历

挑战： 6. 求次小生成树 7. 动态最小生成树（支持动态加边） 8. 最小直径生成树 9. 实现 Borůvka 算法（第三种 MST 算法）