题目
村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井，成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）；另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，其中每个 pipes[j] = [house1j, house2j, costj] 代表用管道将 house1_j 和 house2_j连接在一起的成本。连接是双向的。
请返回 为所有房子都供水的最低总成本 。
示例 1：
输入：n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
输出：3
解释：
上图展示了铺设管道连接房屋的成本。
最好的策略是在第一个房子里建造水井（成本为 1），然后将其他房子铺设管道连起来（成本为 2），所以总成本为 3。
示例 2：
输入：n = 2, wells = [1,1], pipes = [[1,2,1]]
输出：2
解释：我们可以用以下三种方法中的一种来提供低成本的水:
选项1:
在1号房子里面建一口井，成本为1
在房子2内建造井，成本为1
总成本是2。
选项2:
在1号房子里面建一口井，成本为1
-花费1连接房子2和房子1。
总成本是2。
选项3:
在房子2内建造井，成本为1
-花费1连接房子1和房子2。
总成本是2。
注意，我们可以用cost 1或cost 2连接房子1和房子2，但我们总是选择最便宜的选项。
提示：
2 <= n <= 10^4wells.length == n0 <= wells[i] <= 10^51 <= pipes.length <= 10^4pipes[j].length == 3- 1 <= $house1_j$, $house2_j$ <= n
- 0 <= $cost_j$ <= 10^5
- $house1_j$ != $house2_j$
分析
最小生成树的两种实现算法：Prim 和 Kruskal
Prim算法原理：
- 1）以某一个点开始，寻找当前该点可以访问的所有的边；
- 2）在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还- 没有访问的点加入我们的集合，记录添加的边；
- 3）寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入；
- 4）此时由所有边构成的树即为最小生成树。
Kruskal算法原理：
现在我们假设一个图有m个节点，n条边。
- 首先，我们需要把m个节点看成m个独立的生成树，并且把n条边按照从小到大的数据进行排列。
- 在n条边中，我们依次取出其中的每一条边：
- 如果发现边的两个节点分别位于两棵树上，那么把两棵树合并成为一颗树；- 如果树的两个节点位于同一棵树上，那么忽略这条边，继续运行。
- 等到所有的边都遍历结束之后，如果所有的生成树可以合并成一条生成树，那么它就是我们需要寻找的最小生成树，反之则没有最小生成树。
总的来说，Prim算法是以点为对象，挑选与点相连的最短边来构成最小生成树。而Kruskal算法是以边为对象，不断地加入新的不构成环路的最短边来构成最小生成树。
2、堆实现的 Prim 算法 Kruskal
class Solution {
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
// 最小堆，以维护要访问的边的顺序。
PriorityQueue<Pair<Integer, Integer>> edgesHeap =
new PriorityQueue<>(n, (a, b) -> (a.getKey() - b.getKey()));
// 图在邻接表中的表示
List<List<Pair<Integer, Integer>>> graph = new ArrayList<>(n + 1);
for (int i = 0; i < n + 1; ++i) {
graph.add(new ArrayList<Pair<Integer, Integer>>());
}
// 添加索引为0的虚拟顶点，
// 然后在每一栋房子上加一条边，按成本加权
for (int i = 0; i < wells.length; ++i) {
Pair<Integer, Integer> virtualEdge = new Pair<>(wells[i], i + 1);
graph.get(0).add(virtualEdge);
// 使用来自虚拟顶点的边初始化堆。
edgesHeap.add(virtualEdge);
}
// 将双向边添加到图中
for (int i = 0; i < pipes.length; ++i) {
int house1 = pipes[i][0];
int house2 = pipes[i][1];
int cost = pipes[i][2];
graph.get(house1).add(new Pair<Integer, Integer>(cost, house2));
graph.get(house2).add(new Pair<Integer, Integer>(cost, house1));
}
// 从虚拟顶点0开始探索
Set<Integer> mstSet = new HashSet<>();
mstSet.add(0);
int totalCost = 0;
while (mstSet.size() < n + 1) {
Pair<Integer, Integer> edge = edgesHeap.poll();
int cost = edge.getKey();
int nextHouse = edge.getValue();
if (mstSet.contains(nextHouse)) {
continue;
}
// 将新顶点添加到集合中
mstSet.add(nextHouse);
totalCost += cost;
// 扩大下一轮优势候选人的选择范围
for (Pair<Integer, Integer> neighborEdge : graph.get(nextHouse)) {
if (!mstSet.contains(neighborEdge.getValue())) {
edgesHeap.add(neighborEdge);
}
}
}
return totalCost;
}
}
2、并查集实现的 Kruskal 算法
class Solution {
private static final int MAX_N = 10005;
// 并查集数组
private int[] f = new int[MAX_N];
private void init() {
for (int i = 0; i < MAX_N; ++i) {
f[i] = i;
}
}
private int find(int x) {
return x == f[x] ? x : (f[x] = find(f[x]));
}
private void merge(int u, int v) {
f[find(u)] = find(v);
}
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
init();
// 邻接表
List<int[]> edges = new ArrayList<>();
for (int i = 1; i <= n; ++i) {
edges.add(new int[] { 0, i, wells[i - 1] });
}
for (int[] pipe : pipes) {
edges.add(pipe);
}
// 进行排序
edges.sort(Comparator.comparingInt(a -> a[2]));
int ret = 0;
for (int[] edge : edges) {
if (find(edge[0]) != find(edge[1])) {
merge(edge[0], edge[1]);
ret += edge[2];
}
}
return ret;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
