题目
给你一个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
提示：
1 <= points.length <= 1000-10^6 <= xi, yi <= 10^6- 所有点
(xi, yi)两两不同。
解题
前置知识
- 生成树：生成树 指的是「无向图」中，具有该图的 全部顶点 且 边数最少 的 连通子图。
- 最小生成树：最小生成树 指的是「加权无向图」中总权重最小的生成树。
- 切分：
- 切分定理：在一幅连通加权无向图中，给定任意的切分，如果有一条横切边的权值严格小于所有其他横切边，则这条边必然属于图的最小生成树中的一条边。
方法一：Kruskal算法 并查集 优先队列
思路
本题是典型的最小生成树应用题。
Kruskal 算法：是求解「加权无向图」的「最小生成树」的一种算法。
具体做法：
- 把图中所有边按照从小到大排序。
- 把边依次加入最小生成树，如果形成环就跳过。
- 直到选择 N-1 条边为止（N 指顶点数）。
在本题中：共有 个点，有 条边可供选择。对于点 ，连接它们的边的权值为 。
那么我们就可以使用一个优先队列(priQueue)来存储每条边并把它们按照其权值排序。再维护一个并查集(uf)用于在添加某条边之前，确定其连接的两个点之前是否会形成环(isConnected())。
循环从优先队列中取出边：
- 如果当前边连接的两个顶点会形成环，则跳过本次循环。
- 否则使用并查集合并这两个顶点，边的计数(
count)自增，答案(ans)加上该边的权重值。 - 如果
count == n-1或者优先队列为空就退出循环。
代码
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
Queue<Edge> priQueue = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int weight = Math.abs(points[i][0] - points[j][0]) +
Math.abs(points[i][1] - points[j][1]);
priQueue.add(new Edge(i, j, weight));
}
}
UnionFind uf = new UnionFind(n);
int ans = 0, count = 0;
while (!priQueue.isEmpty() && count < n - 1) {
Edge curr = priQueue.poll();
if (uf.isConnected(curr.v1, curr.v2)) continue;
uf.union(curr.v1, curr.v2);
count++;
ans += curr.weight;
}
return ans;
}
static class Edge implements Comparable<Edge> {
public int v1;
public int v2;
public int weight;
public Edge(int v1, int v2, int weight) {
this.v1 = v1;
this.v2 = v2;
this.weight = weight;
}
@Override
public int compareTo(Edge e) {
return Integer.compare(this.weight, e.weight);
}
}
static class UnionFind {
public int groups;
private int[] root;
private int[] rank;
public UnionFind() {}
public UnionFind(int size) {
groups = size;
root = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
root[i] = i;
rank[i] = 1;
}
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (rank[rootP] > rank[rootQ]) {
root[rootQ] = rootP;
} else if (rank[rootP] < rank[rootQ]) {
root[rootP] = rootQ;
} else {
root[rootQ] = rootP;
rank[rootP]++;
}
groups--;
}
public int find(int n) {
return n == root[n] ? n : (root[n] = find(root[n]));
}
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
}
}
class Solution {
static class Edge implements Comparable<Edge> {
int u, v, w;
public Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge e) {
return this.w - e.w;
}
}
static final int INF = 0x3f3f3f3f;
int n, m;
Edge[] edges;
int[] roots;
int find(int x) {
return roots[x] == x ? x : (roots[x] = find(roots[x]));
}
void union(int p, int q) {
roots[find(p)] = find(q);
}
int kruskal() {
Arrays.sort(edges);
roots = new int[n];
for (int i = 0; i < n; ++i) roots[i] = i;
int cnt = 0, res = 0;
for (Edge edge : edges) {
int u = edge.u, v = edge.v, w = edge.w;
if (find(u) != find(v)) {
union(u, v);
res += w;
if (++cnt == n - 1) break;
}
}
return cnt < n - 1 ? INF : res;
}
public int minCostConnectPoints(int[][] points) {
n = points.length;
m = n * (n - 1) / 2;
edges = new Edge[m];
for (int i = 0, u = 0; u < n; ++u) {
for (int v = u + 1; v < n; ++v) {
int w = Math.abs(points[u][0] - points[v][0]) +
Math.abs(points[u][1] - points[v][1]);
edges[i++] = new Edge(u, v, w);
}
}
return kruskal();
}
}
方法二：朴素Prim算法
思路
读题目可以看出这是稠密图求最小生成树，故可以使用：最小生成树 - 朴素Prim模板 求解。
由于所有顶点两两之间都有一条边且不存在重边和自环，所以可以省去初始化的操作直接构造邻接矩阵。
代码
class Solution {
static final int INF = 0x3f3f3f3f;
int n;
int[][] g;
int prim() {
int[] dists = new int[n];
Arrays.fill(dists, INF);
boolean[] vis = new boolean[n];
int res = 0;
for (int i = 0; i < n; ++i) {
int min = -1;
for (int j = 0; j < n; ++j) {
if (!vis[j] && (min == -1 || dists[j] < dists[min])) min = j;
}
if (i != 0) {
if (dists[min] == INF) return INF;
res += dists[min];
}
vis[min] = true;
for (int j = 0; j < n; ++j) dists[j] = Math.min(dists[j], g[min][j]);
}
return res;
}
public int minCostConnectPoints(int[][] points) {
n = points.length;
g = new int[n][n];
for (int u = 0; u < n; ++u) {
for (int v = u + 1; v < n; ++v) {
int w = Math.abs(points[u][0] - points[v][0]) +
Math.abs(points[u][1] - points[v][1]);
g[u][v] = g[v][u] = w;
}
}
return prim();
}
}
方法三：堆优化Prim算法 优先队列
思路
Kruskal 算法步骤：
- 维护两个集合：
visited访问过的顶点，non-visited未访问过的顶点。 - 每次从
non-visited选出一个顶点放入visited，把visited中的顶点看作一个整体，选出它与外界连接的边中，权重最小的一个，这个边就是最小生成树的一个组成部分，这个边连接的另一个节点就是下一次要从non-visited中选出的顶点。
在本题中，维护一个用于存未访问过顶点的优先队列(priQueue)，一个用于标识那些顶点是被访问过了的的数组(visited)。
先把 visited[0] 标为 true 表示选择了先访问第一个顶点 0，随后把顶点 0 与外界连接的边全部加入优先队列中。
循环从优先队列中取出边：
- 如果当前边(
curr)所连接的另一个顶点已经被访问过了，就跳过本次循环。 - 否则，
curr就是visited中最新加入的顶点与外界连接的边中权重最小的，边的计数(count)自增，答案(ans)加上curr的权重值，
再在visited中把curr标记为已访问，内循环把所有顶点curr与外界连接的边全部加入优先队列，然后进行下一次循环。 - 如果
count == n-1或者优先队列为空就退出循环。
代码
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
Queue<Edge> priQueue = new PriorityQueue<>();
for (int i = 1; i < n; i++) {
int weight = Math.abs(points[0][0] - points[i][0]) +
Math.abs(points[0][1] - points[i][1]);
priQueue.add(new Edge(0, i, weight));
}
boolean[] visited = new boolean[n];
visited[0] = true;
int ans = 0, count = 0;
while (!priQueue.isEmpty() && count < n - 1) {
Edge curr = priQueue.poll();
int vertex = curr.v2;
if (visited[vertex]) continue;
ans += curr.weight;
count++;
visited[vertex] = true;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int weight = Math.abs(points[vertex][0] - points[i][0]) +
Math.abs(points[vertex][1] - points[i][1]);
priQueue.add(new Edge(vertex, i, weight));
}
}
return ans;
}
static class Edge implements Comparable<Edge> {
public int v1;
public int v2;
public int weight;
public Edge(int v1, int v2, int weight) {
this.v1 = v1;
this.v2 = v2;
this.weight = weight;
}
@Override
public int compareTo(Edge e) {
return Integer.compare(this.weight, e.weight);
}
}
}
评论区