Day 3：最小生成树（Prim、Kruskal） & 并查集应用

---

📖 一、最小生成树（MST）简介

最小生成树（Minimum Spanning Tree, MST） 是一个 无向连通图 的 最小代价子图，它包含 所有节点，且边的权重总和最小。

📌 最小生成树的性质

1. 连通性：必须包含所有节点，且保证是连通的。
2. 边数 = 节点数 - 1：MST 的边数始终是 V - 1（V 是顶点数）。
3. 权值最小：MST 的边权和最小。

📌 最小生成树的常见算法

算法	核心思想	时间复杂度
Kruskal	贪心 + 并查集，按 边权 递增排序，逐步合并连通分量	O(E log E)（边排序）
Prim	贪心 + 最小堆，按 最小权重 逐步扩展 MST	O(E log V)（优先队列优化）

Kruskal 适用于稀疏图，Prim 适用于稠密图。

---

📖 二、Kruskal 算法（贪心 + 并查集）

适用范围：

• 边稀疏的图（E 边较少）。
• 适用于 离散集问题（如岛屿连通、网络电缆）。

---

🔹 1. 题目：连接所有城市的最低成本（Leetcode 1135）

题目描述： 给定 n 个城市，connections[i] = (u, v, cost) 表示 u-v 之间有条代价 cost 的边。找到最小代价的连接方案，使得所有城市连通，否则返回 -1。

示例

输入: n = 3, connections = [[1,2,5],[1,3,6],[2,3,2]]
输出: 7 （选 [1,2] 和 [2,3]）

---

🔹 2. 思路

1. 贪心 + Kruskal 算法
   • 按边权排序（从小到大）。
   • 使用并查集（Union-Find） 逐步合并两个城市（避免形成环）。
   • 选 n-1 条边后停止，若无法连通所有城市，则返回 -1。

---

🔹 3. 代码实现（Kruskal）

import java.util.*;

public class KruskalMST {
    static class UnionFind {
        int[] parent, 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;
        }

        public int find(int x) {
            if (x != parent[x]) parent[x] = find(parent[x]); // 路径压缩
            return parent[x];
        }

        public boolean union(int x, int y) {
            int rootX = find(x), rootY = find(y);
            if (rootX == rootY) return false; // 已经连通
            if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
    }

    public int minCostToConnectCities(int n, int[][] connections) {
        Arrays.sort(connections, Comparator.comparingInt(a -> a[2])); // 按边权排序
        UnionFind uf = new UnionFind(n);
        int totalCost = 0, edgesUsed = 0;

        for (int[] conn : connections) {
            if (uf.union(conn[0], conn[1])) { // 连接成功
                totalCost += conn[2];
                edgesUsed++;
                if (edgesUsed == n - 1) break; // 最小生成树完成
            }
        }

        return edgesUsed == n - 1 ? totalCost : -1; // 判断是否连通
    }

    public static void main(String[] args) {
        KruskalMST solution = new KruskalMST();
        int[][] connections = {{1,2,5}, {1,3,6}, {2,3,2}};
        int n = 3;
        System.out.println(solution.minCostToConnectCities(n, connections)); // 输出 7
    }
}

---

🔹 4. 代码讲解

1. 并查集（Union-Find）
   • find(x): 查找根节点（带路径压缩）。
   • union(x, y): 合并两个集合（按秩合并）。
2. Kruskal 算法
   • 排序：按边权递增排序。
   • 遍历边：检查 u-v 是否已经连通，若未连通，则加入 MST。
   • 判断最终连通性：若选出的边数为 n-1，返回总代价，否则返回 -1。

✅ 时间复杂度：O(E log E)（排序 + 并查集）

---

📖 三、Prim 算法（贪心 + 最小堆）

适用范围：

• 边稠密的图（E 边较多）。
• 适用于 邻接矩阵/邻接表存储。

---

🔹 1. 代码实现（Prim）

import java.util.*;

public class PrimMST {
    public int minCostToConnectCities(int n, int[][] connections) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : connections) {
            graph.putIfAbsent(edge[0], new ArrayList<>());
            graph.putIfAbsent(edge[1], new ArrayList<>());
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
            graph.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{1, 0}); // 从城市 1 开始
        Set<Integer> visited = new HashSet<>();
        int totalCost = 0;

        while (!pq.isEmpty() && visited.size() < n) {
            int[] cur = pq.poll();
            int city = cur[0], cost = cur[1];

            if (visited.contains(city)) continue; // 已访问
            visited.add(city);
            totalCost += cost;

            for (int[] neighbor : graph.getOrDefault(city, new ArrayList<>())) {
                if (!visited.contains(neighbor[0])) {
                    pq.offer(neighbor);
                }
            }
        }

        return visited.size() == n ? totalCost : -1;
    }

    public static void main(String[] args) {
        PrimMST solution = new PrimMST();
        int[][] connections = {{1,2,5}, {1,3,6}, {2,3,2}};
        int n = 3;
        System.out.println(solution.minCostToConnectCities(n, connections)); // 输出 7
    }
}

---

📖 四、Kruskal vs Prim

算法	核心数据结构	适用场景	时间复杂度
Kruskal	并查集	稀疏图（边少）	O(E log E)
Prim	最小堆（优先队列）	稠密图（边多）	O(E log V)

---

📖 五、总结

🎯 掌握 Kruskal（贪心 + 并查集），适用于离散集合最小代价连接问题。
🎯 掌握 Prim（贪心 + 最小堆），适用于稠密图的最小生成树问题。
🎯 最小生成树的应用：

• 网络连接（最小代价连通所有城市）
• 电网铺设（最少电缆铺设）
• 地图导航（最短成本的道路规划）