并查集¶
一、什么是并查集？¶
并查集是一种简单的集合表示。
它支持以下 3 种操作：
Initial(S)：将集合 S 中的所有元素初始化为一个个单元素集合Union(S, Root1, Root2)：把集合 S 中的子集合 Root2 并入子集合 Root1 中Find(S, x)：查找集合 S 中单元素 x 所在的子集合，并返回子集合的名字
通常用树表示每个子集合，子集合的合并就是树的合并。
子集合 Root2 合并到子集合 Root1，只需要把 Root2 的根节点指向 Root1 的根节点即可。
二、为什么要用并查集？¶
- 并查集主要用于解决一些元素分组的问题
- 并查集可用于管理一系列不相交的集合，执行集合的合并以及搜索元素所在集合
三、如何实现并查集？¶
3.1 集合初始化 Initial(S)¶
void initial (int[] s) {
for (int i = 0; i < s.length; i++) {
s[i] = i;
}
}
初始化后单个元素就是一个集合
集合 S 存储：
[0, 1, 2, 3, 4]
------------------------------------------
集合示意图：
___ ___ ___ ___ ___
| 0 | | 1 | | 2 | | 3 | | 4 |
3.2 子集合合并 Union(S, Root1, Root2)¶
void union(int[] s, int root1, int root2) {
s[root2] = root1;
}
比如合并 0 和 1 得到子集合 0：
集合 S 存储：
[0, 0, 2, 3, 4]
------------------------------------------
集合示意图：
___ ___ ___ ___
| 0 | | 2 | | 3 | | 4 |
^
|
___
| 1 |
再合并 3 和 4 得到子集合 3：
集合 S 存储：
[0, 0, 2, 3, 3]
------------------------------------------
集合示意图：
___ ___ ___
| 0 | | 2 | | 3 |
^ ^
| |
___ ___
| 1 | | 4 |
还可以把子集合 0 和子集合 3 也合并起来：
集合 S 存储：
[0, 0, 2, 0, 3]
------------------------------------------
集合示意图：
___ ___
| 0 | | 2 |
^
/ \
/ \
___ ___
| 1 | | 3 |
^
|
___
| 4 |
3.3 查找子集合 Find(S, x)¶
int find(int[] s, int x) {
while (s[x] != x) {
x = s[x];
}
return x;
}
比如查找 4 所在集合时，过程是这样的：
___________________ _____
| | | |
v | v |
[0, 0, 2, 0, 3]
一直往上找，直到根节点为止，就能得到 4 所在的集合。
3.4 元素合并 Union(S, X1, X2)¶
判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。
- 合并两个元素时，找到它们的根节点合并即可
所以上面的子集合合并代码可以改成这样：
void union(int[] s, int x1, int x2) {
s[find(x2)] = find(x1);
}
四、路径压缩¶
简单的并查集，在某些场景下的性能是比较差的，例如：
- 链条变得越来越长的时候，查找根节点也变得越来越耗时
比如，下面查找元素 5 所在的子集合时，每次都需要经过好几个节点：
___
| 1 |
^
|
___
| 3 |
^
|
___
| 4 |
^
|
___
| 5 |
在并查集链比较长的时候，每次搜索元素的根节点，都比较耗时。
那怎么解决这个问题呢？
- 并查集中只关注根节点，因此可以采用路径压缩，将元素直接指向根节点
而实现的方法也很简单，就是：
- 在查询时，把路径上所有节点的父节点都指向根节点
代码上实现的话，可以采用递归，类似这样：
int find(int[] s, int x) {
if (s[x] == x) {
return x;
} else {
s[x] = find(s, s[x]);
return s[x];
}
}
相当于把上面的一条直链，变成了多叉树：
___
| 1 |
^
/ | \
/ | \
/ | \
___ ___ ___
| 3 | | 4 | | 5 |
经过路径压缩后，就基本解决了链条过长引起的性能问题。
五、按秩合并¶
路径压缩虽然能解决查询时链条过长的问题，但是路径压缩是在查询时才做的。
- 当没有查询时，路径不会压缩，还是会出现链路很长的情况
- 每次查询时，只压缩一条路径，其他路径的链路还是很长
这种情况要如何避免呢？
在两个子集合进行合并时，只要尽量满足：
- 把简单的树往复杂的树上合并
就能避免并查集的树深度过大，影响查询的效率。
比如说，2 个子集合长这样：
___ ___
| 0 | | 3 |
^
|
___
| 1 |
^
|
___
| 4 |
子集合的合并可分为 2 种情况：
3合并到0，树深度是还是2，深度不变0合并到3，树深度变成了3，深度加深了
所以肯定是把深度小的 3 合并到深度大的 0 更好一些，因为这样可以避免节点深度变得更大。
那怎么知道哪个集合的深度更高呢？
- 采用一个额外的数组，记录每个根节点的深度，合并子集合时同时更新
比如说，采用数组 rank 记录节点深度：
- 初始化时，把所有元素的
rank（秩）设为默认值 1 - 合并子集合时，比较两个根节点，把
rank较小合并到较大的上面
代码实现的话就类似这样：
初始化：
void initial (int[] s, int[] rank) {
for (int i = 0; i < s.length; i++) {
s[i] = i;
rank[i] = 1;
}
}
合并子集合：
void union(int[] s, int[] rank, int x1, int x2) {
int root1 = find(x1);
int root2 = find(x2);
if (rank[root1] >= rank[root2]) {
s[root2] = root1;
// 两棵树深度一样的时候，合并起来会加深一层
if (rank[root1] == rank[root2] && root1 != root2) {
rank[root1]++;
}
} else {
s[root1] = root2;
}
}
两棵树深度一样的时候，合并起来会加深一层：
___ ___
| 0 | | 3 |
^ ^
| |
___ ___
| 1 | | 4 |
___
| 0 |
^
/ \
/ \
___ ___
| 1 | | 3 |
^
|
___
| 4 |
按秩合并和路径压缩一起用的时候，路径压缩会影响到 rank 值，导致它不准确。
虽然 rank 值不准确，但是不影响 2 者结合一起用。
总结¶
并查集是一种简单的集合表示，包括 3 种操作：
Initial(S)：将集合 S 中的所有元素初始化为一个个单元素集合Union(S, Root1, Root2)：把集合 S 中的子集合 Root2 并入子集合 Root1 中Find(S, x)：查找集合 S 中单元素 x 所在的子集合，并返回子集合的名字
并查集的作用：
- 并查集主要用于解决一些元素分组的问题
- 并查集可用于管理一系列不相交的集合，执行集合的合并以及搜索元素所在集合
并查集有 2 种方法优化方式：
- 路径压缩：查询时压缩节点路径，直接指向根节点
- 按秩合并：合并时，深度小的合并到深度大的树上面
按秩合并和路径压缩一起用：
- 路径压缩会影响到按秩合并的
rank值，导致它不准确 - 虽然
rank值不准确了，但是不影响 2 者结合一起用
参考¶
《数据结构》王道考研系列
https://zhuanlan.zhihu.com/p/93647900
https://blog.csdn.net/weixin_38279101/article/details/112546053
https://blog.csdn.net/qq_40378034/article/details/103224445
https://destiny1020.blog.csdn.net/article/details/7655764
附录¶
完整代码¶
/**
* 并查集-路径压缩 + 按秩合并
*/
public class UnionFind {
/**
* 父节点存储
*/
private int[] parent;
/**
* 节点深度
*/
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
init(n);
}
/**
* 初始化并查集
*
* @param n 元素个数
*/
private void init(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
/**
* 查找元素
*
* @param x 指定元素
* @return 元素根节点
*/
public int find(int x) {
if (parent[x] == x) {
return x;
} else {
// 路径压缩，会导致 rank 有误差
parent[x] = find(parent[x]);
return parent[x];
}
}
/**
* 合并元素子集合
*
* @param x1 元素
* @param x2 元素
*/
public void union(int x1, int x2) {
int root1 = find(x1);
int root2 = find(x2);
if (root1 == root2) {
return;
}
// 按秩合并
if (rank[root1] > rank[root2]) {
parent[root2] = root1;
} else if (rank[root1] < rank[root2]) {
parent[root1] = root2;
} else {
// 深度一样的时候，合并起来会加深一层
parent[root2] = root1;
rank[root1]++;
}
}
}