力扣labuladong——一刷day83
2024-01-02 16:55:11
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
Prim 算法和 Kruskal 算法都是经典的最小生成树算法,阅读本文之前,希望你读过前文 Kruskal 最小生成树算法,了解最小生成树的基本定义以及 Kruskal 算法的基本原理,这样就能很容易理解 Prim 算法逻辑了。
一、力扣1584. 连接所有点的最小费用
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
List<int[]>[] graph = builderGraph(points,n);
Prim prim = new Prim(graph);
return prim.getWight();
}
public List<int[]>[] builderGraph(int[][] points, int n){
List<int[]>[] graph = new LinkedList[n];
for(int i = 0; i < n; i ++){
graph[i] = new LinkedList<>();
}
for(int i = 0; i < n; i ++){
for(int j = i+1; j < n; j ++){
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
int z = Math.abs(x1 - x2) + Math.abs(y1 - y2);
graph[i].add(new int[]{i,j,z});
graph[j].add(new int[]{j,i,z});
}
}
return graph;
}
class Prim{
private PriorityQueue<int[]> pq;
private boolean[] inMIT;
private int weighSum;
private List<int[]>[] graph;
public Prim(List<int[]>[] graph){
this.graph = graph;
int n = graph.length;
this.pq = new PriorityQueue<int[]>(
(a,b)->{
return a[2] - b[2];
}
);
this.inMIT = new boolean[n];
cut(0);
this.inMIT[0] = true;
while(!pq.isEmpty()){
int cur[] = pq.poll();
int to = cur[1];
int weigh = cur[2];
if(inMIT[to]){
continue;
}
cut(to);
weighSum += weigh;
inMIT[to] = true;
}
}
private void cut(int x){
for(int[] edge : graph[x]){
int to = edge[1];
if(inMIT[to]){
continue;
}
pq.offer(edge);
}
}
public int getWight(){
return this.weighSum;
}
public boolean allConnected(){
for(int i = 0; i < inMIT.length; i ++){
if(inMIT[i] == false){
return false;
}
}
return true;
}
}
}
文章来源:https://blog.csdn.net/ResNet156/article/details/135343139
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!