leetcode 1584 (minimal spanning tree)

Introduction

Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected, undirected graph is a spanning tree with a weight less than or equal to the weight of every other spanning tree. 

Three steps for finding MST using Kruskal’s algorithm

1. Sort all the edges in non-decreasing order of their weight. 
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. 
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

Solution for leetcode 1584 （注意edge case）

class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
int count = 0;
if(n == 0 || n == 1){
return 0;
}
int output = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (a[2] - b[2]));
for(int i = 0; i < n; i++){
//pay attention that j starts from i + 1 because the order doesn't matter
for(int j = i + 1; j < n; j++){
int dis = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
//add i,j instead of point[i] and point[j]
pq.add(new int[] {i, j, dis});
}
}
int remain = n;
Unionfind uf = new Unionfind(n);
while(count < n - 1){
int[] cur = pq.poll();
int first = cur[0];
int second = cur[1];
int dis = cur[2];
if(uf.union(first, second) == true){
output += dis;
count++;
};
}
return output;
}
}
class Unionfind{
int[] father;
public Unionfind(int n){
father = new int[n];
for(int i = 0; i < n; i++){
father[i] = i;
}
}
public boolean union(int i, int j){
int father1 = find(i);
int father2 = find(j);
if(father1 != father2){
father[father1] = father2;
return true;
}
return false;
}
public int find(int i){
if(father[i] == i){
return i;
}
return father[i] = find(father[i]);
}
}

最后

以上就是紧张红牛为你收集整理的leetcode 1584 (minimal spanning tree)的全部内容，希望文章能够帮你解决leetcode 1584 (minimal spanning tree)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。