并查集概念
并查集（Disjoint-set）是一种数据结构，从字面意思上看，“并”，“查”，“集”，可以简单地理解为：“合并”，“查找”，“集合”。
- 集合，就是我们中学所学的一个概念，大概的理解就是把一对元素放在同一个地方。
- 合并，就是并集，意思是把两个集合合并在一起，例如：
$$ { 1, 2, 3, 4 } \cup { 5, 6 } = { 1, 2, 3, 4, 5, 6 } $$
- 查找，需要查找什么？这里的查找指的是要查找这个元素在不在集合中，并且确定这个元素是在哪个集合中
归纳起来就是，并查集这个数据结构就是：
可以进行集合的合并操作可以查找元素在哪个集合中并查集维护的是一堆集合
并查集能解决什么问题
根据并查集的概念可以知道，他能查找一个元素是否在一个集合中，也能进行两个集合之间的合并。
他可以解决一些路径连接或者节点归属的问题。例如：
- 在两个局域网之间原本相互独立的，现在希望这两个局域网可以连接起来，而根据什么规则连接起来，可以使用并查集的合并操作。
- 当需要判断两台主机是否属于同一个局域网中。也可以使用并查集来判断。一些节点归属的问题，都可以使用并查集来解决
并查集的实现
介绍完并查集的一些概念，下面就来分析一下这个数据结构究竟是怎么实现的
根据上面例子来举一个例子：用并查集解决网络连接和网络归属的问题
- 首先我们定义 6 个节点[1，2，3，4，5，6]表示六台主机
- 将[1，2，3，4]四台主机按下图的方式连接起来，取名为局域网 A，其中节点 1 为根节点
- 同样地，将[5，6]两个节点也连接起来，取名为局域网 B，其中节点 5 为根节点
- 这样，主机 1，2，3，4 是属于同一个网络，主机 5，6 是同一个网络
我们把这两个连通的主机分别放在两个集合中。
$$A = {1,2,3,4}$$，$$B = {5, 6}$$
如图所示
当两个局域网搭建完后，现在有人提出了几个问题：
- 1.已知所有的主机网络连接情况(比如上图的局域网 A：主机 3 和 2 是互联的，则可以表示[3, 2]，3 为父节点)，需要计算出一共有多少个网络？
- 2.判断主机 2和主机 4是否在一个局域网内。
- 3.如果主机 4和主机 6不在一个局域网内，怎样将这两个网络连接起来？
通过这几个节点来一步步实现并查集这个数据结构
计算每个节点的父节点（初始化）
首先来看第一个问题。
- 先把所有网络连接情况写出来，分别是：
[0, 2], [2, 1], [2, 3], [4, 5]，其中: 数组的第一个元素是父节点，第二个元素是子节点。
- 第二步：用一维数组来记录下所有元素的父节点
- 当记录下所有元素的父节点时，由于根节点上不存在父节点，所以有多少个局域网的问题就可以转移为：数组中有多少个不存在父节点的元素
问题分析完了，开始用代码实现~
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
33
34
35
36
37
38
39
40
41
42
|
const COMPUTER_NUM = 6;
const connectLine = [
[0, 2],
[2, 1],
[2, 3],
[4, 5],
];
function init() {
const arr = [];
for (let i = 0; i < COMPUTER_NUM; i++) {
arr.push(-1);
}
return arr;
}
function fillParentNode(parentArr, connectLine) {
connectLine.forEach((item) => {
parentArr[item[1]] = item[0];
});
}
function findParentNum(parentArr) {
return parentArr.filter((index) => index === -1).length;
}
const parentArr = init();
fillParentNode(parentArr, connectLine);
console.log(parentArr);
const parentNum = findParentNum(parentArr);
console.log(`there are ${parentNum} networks`);
|
可以看到，先声明了一个用于装父节点的数组，并且默认值为-1，后面通过遍历讲所有主机的父节点记录到数组中，最后通过遍历数组统计父节点值还是-1 的数量，这个数量就是局域网的个数。
自此，第一个问题已经解决。
查找两个元素的根节点（查找节点）
继续来看看第二个问题：判断主机 2和主机 4是否在一个局域网内，再来回看上面的一个图，要判断两个主机是否在一个局域网内，问题可以转化为：这两个主机的根节点是否相同，如果相同则在同一个局域网中。
解决办法已经找到，接下来用代码实现，从上面已经实现的代码继续写下去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
function findRoot(child, parentArr) {
let result = child;
while (parentArr[result] !== -1) {
result = parentArr[result];
}
return result;
}
const tag_2 = findRoot(1, parentArr);
const tag_4 = findRoot(3, parentArr);
console.log(`两台主机${tag_2 === tag_4 ? "在" : "不在"}同一个网络中`);
|
通过不停地往上查找父节点，直到查找到定义元素的根节点后停止并返回。如果两台主机的根节点是相同的，则这两台主机在同一个集合中~反之则不在。
第二个问题也解决了。现在我们所定义的方法已经能够进行初始化和排序操作了。
两个网络连接（集合合并）
解决了查找的问题，接下来看第三个问题：
如果主机4和主机6不在一个局域网内，怎样将这两个网络连接起来？
要将两个网络连接起来的方法有很多，两个网络任意一个主机连接起来都会有变成一个局域网。
但我们需要找出他们之间效率最高的连接方法，如果我按下图的方法进行连接。
图中将局域网 B 的根结点连接到局域网 A 的 4 结点中，虽然两个网络连接起来了，但是这个网络的高度增加了（树的高度增加了），树的高度越高，查找越慢。从效率上看这种连接方法是不可取的。
要使树的效率高，应当减少树的高度。所依可以从两个树的根节点上连接，如下图
从第二个问题中已经实现了查找根元素的方法，接下来只要实现一个方法将两个根元素合并起来就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
function unionSet(x, y, parentArr) {
const x_root = findRoot(x, parentArr);
const y_root = findRoot(y, parentArr);
if (x_root === y_root) {
return false;
} else {
parentArr[x_root] = y_root;
return true;
}
}
unionSet(3, 5, parentArr);
console.log(parentArr);
|
到这里，两个网络已经成功合并起来了。
优化合并（路径压缩）
从代码中可以看到，虽然从根节点上连接起来，但是它的时间复杂度为O(n)，当有多个网络需要连接起来时，性能可能会不够好。
再来分析一下，并查集主要的函数是并(union) 和 查（find）。
查找方法中，我们只需要找到元素的根节点,无需关心元素的父节点，那么我们在记录节点关系的时候只要记住节点的根节点就行了，如下图：
接下来修改一下代码：
合并方法修改
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
|
function unionSet(x, y, parentArr, rankArr) {
const x_root = findRoot(x, parentArr);
const y_root = findRoot(y, parentArr);
if (x_root === y_root) {
return false;
} else {
if (rankArr[x_root] > rankArr[y_root]) {
parentArr[y_root] = x_root;
} else if (rankArr[x_root] < rankArr[y_root]) {
parentArr[x_root] = y_root;
} else {
parentArr[x_root] = y_root;
rankArr[y_root]++;
}
return true;
}
}
|
初始化方法修改
1
2
3
4
5
6
7
8
9
10
11
|
function init() {
const arr = [];
const rankArr = [];
for (let i = 0; i < COMPUTER_NUM; i++) {
arr.push(-1);
rankArr.push(0);
}
return [arr, rankArr];
}
|
记录父节点的方法修改
1
2
3
4
5
6
|
function fillParentNode(parentArr, rankArr, connectLine) {
connectLine.forEach((item) => {
unionSet(item[1], item[0], parentArr, rankArr);
});
}
|
代码修改完了，现在来试一下
1
2
3
|
unionSet(3, 5, parentArr, rankArr);
console.log(parentArr);
|
合并后的网络如下图：
显然与为优化相比，树的高度减少了。而且时间复杂度也变为O(a(n))
完整代码
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
function init() {
const arr = [];
const rankArr = [];
for (let i = 0; i < COMPUTER_NUM; i++) {
arr.push(-1);
rankArr.push(0);
}
return [arr, rankArr];
}
function fillParentNode(parentArr, rankArr, connectLine) {
connectLine.forEach((item) => {
unionSet(item[1], item[0], parentArr, rankArr);
});
}
function findParentNum(parentArr) {
return parentArr.filter((index) => index === -1).length;
}
function findRoot(child, parentArr) {
let result = child;
while (parentArr[result] !== -1) {
result = parentArr[result];
}
return result;
}
function unionSet(x, y, parentArr, rankArr) {
const x_root = findRoot(x, parentArr);
const y_root = findRoot(y, parentArr);
if (x_root === y_root) {
return false;
} else {
if (rankArr[x_root] > rankArr[y_root]) {
parentArr[y_root] = x_root;
} else if (rankArr[y_root] > rankArr[x_root]) {
parentArr[x_root] = y_root;
} else {
parentArr[x_root] = y_root;
rankArr[y_root]++;
}
return true;
}
}
const COMPUTER_NUM = 6;
const [parentArr, rankArr] = init();
fillParentNode(parentArr, rankArr, connectLine);
unionSet(3, 5, parentArr, rankArr);
|
小结
本文主要介绍了并查集的概念，作用和实现。并查集他是一种数据结构，能查找出某两个节点是否在同一个集合中。
并查集的关键是
可以进行集合的合并操作可以查找元素在哪个集合中并查集维护的是一堆集合
若文章中有不严谨或出错的地方请在评论区域指出~
参考
- 并查集（Disjoint-set）
- 并查集能干点啥？
