[特殊字符] 蓝桥杯 Java B 组 之最小生成树（Prim、Kruskal） 并查集应用

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（贪心 + 最小堆），适用于稠密图的最小生成树问题。
🎯 最小生成树的应用：

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