并查集
并查集,Disjoint-Set,或者通俗一点,叫做MergeFind-Set,是一种可以动态维护若干个不重叠的集合,并支持集合之间的合并与查询的数据结构。
集体来说,并查集支持下列两个操作:
-
Find,查询元素所属集合
-
Merge,将两个元素所属集合合并
一般来说,为了具体实现,我们将每一个集合选择一个固定的元素,作为整个集合的代表
所以,假设我们的元素是一堆整数,则,可以有
// N需要根据实际情况调整,grp是group的缩写
int grp[N];
初始化则设每一元素所在的组是其本身
for (int i = 0; i <= n; ++i) grp[i] = i;
做完了准备工作,我们需要思考如何合并?
考虑我们可以使用树形结构来储存,则,每一个树根都应该满足grp[root] = root
。
于是我们只需要修改树根就行了,即grp[root(x)] = root(y)
那么,问题来了,如何寻找根?
回到上述定义中的树形结构及其性质,则很容易可以推出一个递归算法:
int find(int x) {
if (grp[x] != x) return find(grp[x]);
return x;
}
于是,合并的算法也就可以写出来了
int merge(int x, int y) {
grp[find(x)] = find(y);
}
优化
优化方案有3:路径压缩
,启发式合并
,按秩合并
。
路径压缩
其实,我们把整个grp
的关系链画出来
1-->2;
1-->3;
2-->4;
4-->5;
实际上,我们可以不关注树的形状,意味着上图中的树实际上等价于
1-->2;
1-->3;
1-->4;
1-->5;
这样,我们就可以在find
中将这个元素直接连接到其父节点上
则有
int find(int x) {
if (grp[x] != x) return grp[x] = find(grp[x]);
return x;
}
其实很多时候,只用路径压缩就已经够了
启发式合并
看上去很高级的名字,其实原理很简单
我们新建一个cnt
数组,由于记录每一个元素所在集合中有多少个元素,在合并时,将元素多的作为根,则可以相对优化。
但是,毕竟是启发式合并,元素多的并不一定层数少,这是一个概率问题……
但好处是,启发式合并可以和路径压缩一起使用,这比只使用路径压缩快了一些,并且代码复杂度比较简单。所以我就不提供参考代码了
按秩合并
这里的秩就是指树的深度,那么,为了优化,很明显,我们需要将层数少的合并到层数多的树中,且层数少的合并到层数多的并不会影响层数多的层数。
但是,如果两者层数相等呢?
举个例子,我们要合并1
和4
。
1-->2;
1-->3;
4-->5;
那么由于两棵树层数相等,所以无论哪一个作为主树都可(假设我们以1为主树)
则合并之后应该时
1-->2;
1-->3;
1-->4;
4-->5;
可以发现,层数变多了……所以说,秩需要+1
分析完毕,代码该如何写?
首先时初始化,由于刚开始每一个元素都是一颗树,所以秩为1
int rank[N]; // 储存每一个元素的秩
for (int i = 0; i <= n; ++i) {
rank[i] = 1;
grp[i] = i;
}
寻找的代码不变
合并代码如下
void merge(int x, int y) {
int gx = find(x), gy = find(y);
if (rank[gx] <= rank[gy])
grp[gx] = gy;
else
grp[gy] = gx;
if (rank[gx] == rank[gy] && gx != gy) // 防止合并相同元素
++rank[y];
}
按秩合并其实并不能和路径压缩一起使用,因为路径压缩会破坏其秩的大小
扩展
并查集也可以应用在最小生成树算法中,其中一个比较经典的算法:kruskal算法就用到了并查集的辅助。这方面可以参考其他资料,这里不做过多的展开
练习
所以,并查集你应该掌握了,下课!