题目定义：
给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的
曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
示例 1：
输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。
示例 2：
输入：points = [[3,12],[-2,5],[-4,1]]
输出：18
示例 3：
输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4
示例 4：
输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000
示例 5：
输入：points = [[0,0]]
输出：0
方式一(kruskal)：
class Solution {
public int minCostConnectPoints(int[][] points) {
int length = points.length,ans = 0,num = 0;
List<Edge> edgs = new ArrayList<>();
UnionFind unionFind = new UnionFind(length);
for(int i = 0; i < length; i++)
for(int j = i + 1; j < length; j++)
edgs.add(new Edge(dist(points,i,j),i,j));
edgs.sort(Comparator.comparingInt((Edge e)->e.len));
for(Edge edg : edgs){
if(unionFind.union(edg.x,edg.y)){
++num;
ans += edg.len;
if(num == length)
break;
}
}
return ans;
}
private int dist(int[][] points,int x,int y){
return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
}
}
class UnionFind{
int[] parent;
int[] rank;
UnionFind(int n){
parent = new int[n];
rank = new int[n];
for(int i = 0; i < n; i++){
parent[i] = i;
rank[i] = 1;
}
}
boolean union(int x,int y){
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY)
return false;
if(rootX < rootY){
rootX = rootX ^ rootY;
rootY = rootX ^ rootY;
rootX = rootX ^ rootY;
}
rank[rootX] += rank[rootY];
parent[rootY] = rootX;
return true;
}
private int find(int index){
if(parent[index] != index)
parent[index] = find(parent[index]);
return parent[index];
}
}
class Edge{
int len,x,y;
Edge(int len,int x,int y){
this.len = len;
this.x = x;
this.y = y;
}
}
方式二(prime)：
class Solution {
public int minCostConnectPoints(int[][] points) {
int[] lowCost = new int[points.length];
int checkPoint = 0;
int cost = 0;
Arrays.fill(lowCost,Integer.MAX_VALUE);
lowCost[0] = 0;
for(int i = 0; i < points.length - 1; i++){
int minCost = Integer.MAX_VALUE;
int minPoint = 0;
for(int j = 0; j < points.length; j++){
if(lowCost[j] != 0){
lowCost[j] = Math.min(lowCost[j],dist(points,checkPoint,j));
if(lowCost[j] < minCost){
minCost = lowCost[j];
minPoint = j;
}
}
}
checkPoint = minPoint;
lowCost[minPoint] = 0;
cost += minCost;
}
return cost;
}
private int dist(int[][] points,int x,int y){
return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
}
}
参考：
https://leetcode-cn.com/problems/min-cost-to-connect-all-points/