题目
给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
克鲁斯克尔算法
克鲁斯克尔算法（Kruskal’s algorithm），是一种用来查找最小生成树的算法，但算法的实现不一样，它是通过对权值从小到大顺序排列来查找最小生成树的。
1.将原图中所有的边按权值从小到大排序。
2.从权值最小的边开始，如果这条边连接的两个节点于图中不在同一个已连接的边中，则记录该顶点为已选择。
3.重复步骤2，直至图中所有的节点都连通，就找到了连通图的最小生成树。
对于节点之间是否连接，属于连通性问题，可以采用并查集来实现，具体细节可以看我以前的博客
基于以上的思路，我们可以得出以下的算法：
并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class UnionFind{
constructor(n) {
this.n = n;
this.f = new Array(n).fill(0).map((ele, index) => index);
}
find(x) {
if (this.f[x] === x) {
return x;
}
this.f[x] = this.find(this.f[x]);
return this.f[x];
}
union(x, y) {
let fx = this.find(x), fy = this.find(y);
if (fx === fy) {
return false;
}
this.f[fy] = this.f[fx];
return true;
}
}
|
算法主体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| var minCostConnectPoints = function(points) {
for(let i = 0; i < n; i++) {
for(let j = i + 1; j < n; j++) {
edges.push([dist(i, j), i, j]);
}
}
edges.sort((a, b) => a[0] - b[0]);
const dist = (x, y) => {
return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
}
const n = points.length;
const uni = new UnionFind(n);
const edges = [];
let ret = 0, num = 1;
for(const [length, x, y] of edges) {
if (uni.union(x, y)) {
ret += length;
num++;
if (num === n) {
break;
}
}
}
return ret;
}
|
按秩合并
上面的并查集算法只是加入了路径压缩，但是这个路径压缩仅仅是减少了我们并查集中维护的连通性树的深度，而并不是我们实际连接的树的深度，所以我们引入了一个新的概念，叫做秩。
我们将连接过程中的产生的每个树的实际深度都叫做秩，我们要做的就是在合并的时候尽量将秩小的树连接到秩大的树的根节点，如果将要合并的两个树的秩相同，就挑选其中一个，插入另一个树的根节点，另一个树的秩加一，这样就可以保证最后生成出的树的秩是最小的。
所以我们改造下我们的并查集算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class UnionFind{
constructor(n) {
this.n = n;
this.rank = new Array(n).fill(1);
this.f = new Array(n).fill(0).map((ele, index) => index);
}
find(x) {
if (this.f[x] === x) {
return x;
}
this.f[x] = this.find(this.f[x]);
return this.f[x];
}
union(x, y) {
let fx = this.find(x), fy = this.find(y);
if (fx === fy) {
return false;
}
if (this.rank[fx] < this.rank[fy]) {
[fx, fy] = [fy, fx];
} else if (this.rank[fx] === this.rank[fy]) {
this.rank[fx]++;
}
this.f[fy] = this.f[fx];
return true;
}
}
|
Prim算法
Prim算法的步骤包括：
- 将一个图分为两部分，一部分归为点集U，一部分归为点集V，U的初始集合为{V1}，V的初始集合为{ALL-V1}。
- 针对U开始找U中各节点的所有关联的边的权值最小的那个，然后将关联的节点Vi加入到U中，并且从V中删除（注意不能形成环）。
- 递归执行步骤2，直到V中的集合为空。
- U中所有节点构成的树就是最小生成树。
算法的基本实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| var minCostConnectPoints = function(points) {
const dist = (x, y) => {
return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
}
const n = points.length;
const visited = [];
const unVisited = new Array(n).fill(0).map((ele, index) => index);
visited.push(unVisited.shift()) ;
let ret = 0;
while(visited.length < n) {
let min = Number.MAX_SAFE_INTEGER;
let next = unVisited[0];
for(let i = 0; i < visited.length; i++) {
for(let j = 0; j < unVisited.length; j++) {
const tempDist = dist(visited[i], unVisited[j]);
if (min > tempDist) {
min = tempDist;
next = j;
}
}
}
ret += min;
visited.push(unVisited.splice(next, 1));
}
return ret;
}
|
上面这个版本是对算法最基本的实现，但是其实还有很多优化的空间。
比较
方法上：Kruskal在所有边中不断寻找最小的边，Prim在U和V两个集合之间寻找权值最小的连接，共同点是构造过程都不能形成环。
时间上：Prim适合稠密图，复杂度为O(n * n)，因此通常使用邻接矩阵储存，复杂度为O(e * loge)，而Kruskal多用邻接表，稠密图 Prim > Kruskal，稀疏图 Kruskal > Prim。
空间上： Prim适合点少边多，Kruskal适合边多点少。