Day 3：最小生成树（Prim、Kruskal） & 并查集应用
📖 一、最小生成树（MST）简介
最小生成树（Minimum Spanning Tree, MST） 是一个 无向连通图 的 最小代价子图，它包含 所有节点，且边的权重总和最小。
📌 最小生成树的性质
- 连通性：必须包含所有节点，且保证是连通的。
- 边数 = 节点数 - 1：MST 的边数始终是
V - 1（V是顶点数）。 - 权值最小：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. 思路
- 贪心 + 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. 代码讲解
- 并查集（Union-Find）
find(x): 查找根节点（带路径压缩）。union(x, y): 合并两个集合（按秩合并）。
- 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（贪心 + 最小堆），适用于稠密图的最小生成树问题。
🎯 最小生成树的应用：
- 网络连接（最小代价连通所有城市）
- 电网铺设（最少电缆铺设）
- 地图导航（最短成本的道路规划）
