并查集(Disjiont-set)
[TOC]
更新
- 5/23/2018 更新路径压缩代码
简介
wiki上关于并查集的简介
在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：
- Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- Union：将两个子集合并成同一个集合。
并查集主要用于解决动态连通性问题(我也不懂是什么问题).
我们用一个代表来标识一个不交集. 通常我们不关心哪个成员作为代表, 但是对于属于同一个集合的两个变量, 查询应该得到相同的代表.
举个栗子. 假如有一个大型的计算机网络, 其中有很多台计算机, 如果计算机a与计算机b连通, b与c连通, 那么a与c连通. 对于网络中的两台计算机p, q我们可能有这些操作: 判断p, q是否连通find(p) == find(q); 在p, q之间建立一条路线使两者连通union(p, q).
通过上面的例子不难看出连通是一种等价关系, 它有以下性质:
- 自反性: p与p是连通的
- 对称性: p与q连通, 则q与p连通
- 传递性: p与q连通且q与r连通, 则p与r连通
算法实现
首先我们用一个数组记录所有元素, 对于set[i] == k , i表示一个元素, k表示元素所属的集合, 通常可以指向或者间接指向集合的代表来表示属于这个集合. 当set[i] == i是表明i是一个根节点.
set[i] ==k可以理解为i, k之间有一条连通的路线, 被称为链接.
初始化
让所有元素指向自己, 表示属于不同的集合, 此时集合中每个元素都是一个根节点
const int SIZE = 100001;
int set[SIZE];
void init(int n) {
for (int i = 1; i <= n; ++i)
set[i] = i;
}
Find
从x向上查找, 直到找到元素的根节点set[i] == i, 此根节点就表示这个集合
//循环写法
int findSet(int x) {
while (set[x] != x)
x = set[x]
return x;
}
//递归写法
int findSet(int x) {
if (x != set[x])
find(set[x]);
else
return x;
}
Union
把两个不同的点连起来, 对于x ,y两个点来说, 相当与把x, y所在集合合并(传递性), 即x, y所在集合所以元素都连通. 所以我们可以找到两个集合的代表(根节点), 然后把代表合并即可.
void union_set(int x, int y){
//分别找到x, y所在集合的代表
int rootX = find(x);
int rootY = find(y);
//如果已经在一个集合中 直接return 不进行合并操作
if (rootX == rootY) return;//这句此处看起来无关痛痒, 但是在后面的算法优化中很重要
set[rootX] = rootY;//选取rootY为新集合的代表, 把x所在集合合并到y所在集合
}
我们在选取谁合并到谁时是随便选取的, 实际上合理的选取能够很好地优化算法.
图示
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 9 | 2 | 5 | 9 | 1 | 9 | 7 |
findSet(6)即为set[set[set[set[6]]]] ==1, findSet(7)即为set[set[7]] == 9
unionSet(6, 7)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 9 | 1 | 1 | 9 | 2 | 5 | 9 | 1 | 9 | 7 |
则rootX = 1, rootY = 9, 即set[1] = 9
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 9 | 1 | 1 | 9 | 2 | 5 | 9 | 1 | 9 | 7 |
算法优化
加权
上面提到合并是随意选取的, 那么怎么选取可以优化算法呢. 考虑find算法的过程, 从低向上查找代表, 那么树的高度就决定了find的快慢. 所以我们合并时可以考虑把比较矮的树合并到比较高的树上, 这样可以有效降低树的高度, 从而达到优化算法的目的.
这是一种加权并查集, 即每个代表会记录该集合的大小(元素多少)作为代表的权. 合并时我们把权小的代表所在集合(小树)合并到权大的代表所在集合(大树).
启发式合并可以保证对数级别的性能O(logN).
int size[SIZE];//记录对应集合的元素个数 开始时需要初始化为0
void unionSet(int x, int y) {
int rootX = findSet(x);
int rootY = findSet(y);
//这个return特别重要, 如果忽略, 会出现同一个树的大小加倍的错误
if (rootX == rootY)
return;
//比较两个树的大小 小树合并到大树上
if (size[rootY] > size[rootX]) {
set[rootX] = rootY;
size[rootY] += size[rootX];
} else {
set[rootY] = rootX;
size[rootX] += size[rootY];
}
}
加权还有很多其他的用途, 比如统计一个集合的元素个数, 对集合元素分类.
启发式合并
和加权的思路一样, 只是记录的是树的高度, 更加直接
int rank[SIZE];//记录树的高度
void unionSet(int x, int y) {
int rootX = findSet(x);
int rootY = findSet(y);
if (rank[rootX] > rank[rootY]) {
set[rootY] = rootX;
} else {
set[rootX] = rootY;
if (rank[rootY] == rank[rootX])
rank[rootY]++;
}
}
加权与启发式合并图示
unionSet(6, 7), 因为6所在树比7所在树高且大, 所以此时set[9] = 1.
可以看到相比没有优化的算法, 这种合并方式有效地降低了树高.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 9 | 2 | 5 | 9 | 1 | 1 | 7 |
路径压缩
既然把树高降低能优化算法, 那么我们能在find中降低树高吗.
我们可以在find中把查找路径上遇到的所有节点都直接链接到根节点, 从而实现路径压缩, 把树高降低.
代码十分简单, 甚至不比上面的复杂. 时间复杂度非常接近但是没有达到1
int findSet(int x) {
if (set[x] != x)
return set[x] = findSet(set[x]);//这里最终返回都是根节点
return x;//一定是根节点返回这句
//然后根据根节点的返回, 更新查找路径上其他节点
}
//一种很简洁的写法
int findSet(int x) {
return (set[x] == x) ? x : (set[x] = findSet(set[x]));
}
路径压缩图示
unionSet(6, 7)(没有优化的合并)
先会调用findSet(6), findSet(7), 查找路径上的所以元素都会直接和根节点链接
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 9 | 1 | 1 | 9 | 1 | 9 | 7 |
之后set[1] = 9
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 9 | 1 | 1 | 9 | 1 | 1 | 9 | 1 | 9 | 7 |
小结
- 路径压缩加上启发式合并就是并查集算法的最优解.
- 一般来说用路径压缩算法就足够了, 可以不再用启发式合并或者加权.(减少代码量)
