题解 | 最小生成树

解题思路：

使用 $Kruskal$ 算法求最小生成树：
- 将所有边按权重排序
- 使用并查集维护节点的连通性
- 依次选择权重最小的边，如果不会形成环就加入最小生成树
并查集优化：
- 使用路径压缩优化 find 操作
- 使用按秩合并优化 union 操作
算法步骤：
- 初始化并查集
- 对边按权重排序
- 遍历边，使用并查集判断是否形成环
- 统计总成本和使用的边数
- 检查图的连通性

代码

c++
java
python

class Solution {
public:
    // 并查集数据结构
    class UnionFind {
    private:
        vector<int> parent;
        vector<int> rank;
        
    public:
        UnionFind(int n) {
            parent.resize(n + 1);
            rank.resize(n + 1);
            for(int i = 0; i <= n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }
        
        int find(int x) {
            if(parent[x] != x) {
                parent[x] = find(parent[x]); // 路径压缩
            }
            return parent[x];
        }
        
        bool unite(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY) {
                return false;
            }
            
            // 按秩合并
            if(rank[rootX] < rank[rootY]) {
                swap(rootX, rootY);
            }
            parent[rootY] = rootX;
            if(rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
            return true;
        }
    };
    
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // 将边按照权重排序
        sort(cost.begin(), cost.end(), 
             [](const vector<int>& a, const vector<int>& b) {
                 return a[2] < b[2];
             });
        
        UnionFind uf(n);
        int totalCost = 0;
        int edgesUsed = 0;
        
        // Kruskal算法
        for(const auto& edge : cost) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            
            if(uf.unite(from, to)) {
                totalCost += weight;
                edgesUsed++;
                
                if(edgesUsed == n - 1) {
                    break;
                }
            }
        }
        
        // 检查是否所有节点都已连接
        int root = uf.find(1);
        for(int i = 2; i <= n; i++) {
            if(uf.find(i) != root) {
                return -1;
            }
        }
        
        return totalCost;
    }
};

import java.util.*;

public class Solution {
    // 并查集数据结构
    class UnionFind {
        private int[] parent;
        private int[] rank;
        
        public UnionFind(int n) {
            parent = new int[n + 1];
            rank = new int[n + 1];
            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]) {
                int temp = rootX;
                rootX = rootY;
                rootY = temp;
            }
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
            return true;
        }
    }
    
    public int miniSpanningTree(int n, int m, int[][] cost) {
        // 将边按照权重排序
        Arrays.sort(cost, (a, b) -> a[2] - b[2]);
        
        UnionFind uf = new UnionFind(n);
        int totalCost = 0;
        int edgesUsed = 0;
        
        // Kruskal算法
        for (int[] edge : cost) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            
            // 如果这条边不会形成环，则加入最小生成树
            if (uf.union(from, to)) {
                totalCost += weight;
                edgesUsed++;
                
                // 如果已经使用了n-1条边，说明最小生成树已经完成
                if (edgesUsed == n - 1) {
                    break;
                }
            }
        }
        
        // 检查是否所有节点都已连接
        int root = uf.find(1);
        for (int i = 2; i <= n; i++) {
            if (uf.find(i) != root) {
                return -1; // 图不连通
            }
        }
        
        return totalCost;
    }
}

class Solution:
    class UnionFind:
        def __init__(self, n):
            self.parent = list(range(n + 1))
            self.rank = [1] * (n + 1)
        
        def find(self, x):
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])  # 路径压缩
            return self.parent[x]
        
        def union(self, x, y):
            root_x = self.find(x)
            root_y = self.find(y)
            if root_x == root_y:
                return False
            
            # 按秩合并
            if self.rank[root_x] < self.rank[root_y]:
                root_x, root_y = root_y, root_x
            self.parent[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
            return True
    
    def miniSpanningTree(self, n: int, m: int, cost: List[List[int]]) -> int:
        # 将边按照权重排序
        cost.sort(key=lambda x: x[2])
        
        uf = self.UnionFind(n)
        total_cost = 0
        edges_used = 0
        
        # Kruskal算法
        for from_node, to_node, weight in cost:
            if uf.union(from_node, to_node):
                total_cost += weight
                edges_used += 1
                
                if edges_used == n - 1:
                    break
        
        # 检查是否所有节点都已连接
        root = uf.find(1)
        for i in range(2, n + 1):
            if uf.find(i) != root:
                return -1
        
        return total_cost

算法及复杂度分析：

算法： $Kruskal$ 算法，并查集
时间复杂度： $\mathcal{O}(m \log m)$
- 排序需要 $\mathcal{O}(m \log m)$
- 并查集操作接近 $\mathcal{O}(1)$
空间复杂度： $\mathcal{O}(n)$
- 并查集需要 $\mathcal{O}(n)$ 的空间

注意事项：

需要检查图是否连通
最小生成树应该有 $n-1$ 条边
使用并查集时要注意路径压缩和按秩合并的优化
边的权重可能相同，但不影响算法正确性