因为工作的关系,不得不学习了几种算法,好久不用又忘记了,这是一篇复习文章。
并查集回答的是连接问题,比如说从 a 城到 b 城有没有路,能回答有或者没有,但是不能回答具体的路是那几条,该怎么走;再比如说 a、z 这 2 个人能否通过共同好友的名片分享来加上微信。
并查集是解决点与点之间的关系,遇到实际问题的时候,需要我们进行转换成点与点,也就是建模。在数据结构上一般用数组来存储这些点。
let id = new Array(n); // 先用一个数组保留每个元素的父子关系,容量为 n
for (var i = 0; i < n; i++) {
id[i] = i; // 初始值是数组索引的位置,表示各不相连
}
比如上面的微信加好友的例子中,我们需要把人与数字进行一下映射。看一下实际的例子。
let map = {
a: 0, // 假设 a b c d 都是人,在数组的位置依次为 0 1 2 3
b: 1,
c: 2,
d: 3
};
let uf = new UnionFind(4, i => map[i]);
uf.union("a", "b");
uf.union("b", "c");
console.log(uf.connected("a", "c")); // true
并查集的实现代码不多,去掉一些非核心代码如下:
<script>
function UnionFind(n, key) {
var id, sz;
key =
key ||
function(a) {
return a;
};
id = new Array(n);
sz = new Array(n);
for (var i = 0; i < n; i++) {
id[i] = i;
sz[i] = 1;
}
this.find = function(p) {
while (p != id[p]) {
id[p] = id[id[p]]; // 路径压缩
p = id[p];
}
return p;
};
this.connected = function(p, q) {
p = key(p);
q = key(q);
return this.find(p) === this.find(q);
};
this.union = function(p, q) {
p = key(p);
q = key(q);
var i = this.find(p),
j = this.find(q);
if (i === j) return;
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i]; // 基于 size 的优化
} else {
id[j] = i;
sz[i] += sz[j];
}
};
}
let map = {
a: 0,
b: 1,
c: 2,
d: 3
};
let uf = new UnionFind(4, i => map[i]);
uf.union("a", "b");
uf.union("b", "c");
console.log(uf.connected("a", "c"));
</script>
优化手段
- 基于 size 的优化
- 基于 rank 的优化
- 路径压缩
《并查集的正确使用姿势》有一个想法