【数据结构与算法】并查集
定义
并查集被认为是最简洁而优雅的数据结构之一。顾名思义,并查集是一类集合,它支持合并和查询两种操作
从集合论出发
在集合 上定义一个等价关系(自反、对称、传递)~
,a~b
表示元素a
与b
等价。
根据等价关系,可以将集合 划分为若干个等价类 :
- 一个元素
a
的等价类是 的一个子集,它包含所有与a
有关系的元素; - 等价类互不相见,所有等价类的并集就是集合 ;
- 要确定是否
a~b
,只需要验证a
和b
是否在同一个等价类中。
初始时,有N
个元素,每个元素自成一个集合,元素互不相同,集合互不相交
1 | {a},{b},{c},{d} ... {n} |
对这些集合可以进行两种运算:
Find
给定元素
a
,返回该元素所在集合的名字,即查询该元素属于哪个等价类。Union
给定一对元素
a
和b
,添加关系a~b
;若这对元素不在同一个等价类中,由于等价关系的传递性,该运算将合并含有a
和b
的两个等价类形成一个新的等价类。1
{a, b},{c},{d} ... {n}
以上是并查集在集合论中的理论定义,有点抽象,为了将并查集具象化,可以映射到图论中。
引入图论
对于一个无向图,它的所有节点构成点集V
、所有边构成边集E
。若V
中两个节点a
和b
之间存在一条边,那么称a
和b
是连通关系。显然连通关系是集合V
上的一个等价关系。根据连通关系,可以将点集V
划分为若干个等价类,称之为连通分量。
那么上述操作就变成了:
Find
给定某点
a
,查询a
所属的连通分量,可以用来判断两点是否属于同一连通分量Union
给定一对点
a
和b
,在它们之间连接一条边,使两点连通,那么各自对应的连通分量也会连通成为一个新的连通分量。
从而我们为并查集在图论中找到了对应的实际意义:并查集可以用来表示和求解图中的连通性问题。
构造
显然我们不关心也不需要知道等价类集合的名字,只需要在该等价类中选出一个代表元素x
,给x
赋予一个特殊地位,让集合中的其他元素从属于它。这就是并查集的重要思想所在。
现实来说,如果把集合比喻成一个帮派,那么代表元素就是选出的帮主,帮派中的其他帮众从属于帮主,帮众的事就是帮主的事。
那么上述两种操作就变成了:
查询
给定元素
a
,返回该元素的集合的代表元素;询问
a
所在帮派的帮主是谁,有事找帮主就行。合并
给定一对元素
a
和b
,合并a
和b
所在集合,在原来的两个代表元素中,选出新的代表元素。a和b想搞事情,必须由各自帮主出面,两个帮主比武后,按照约定好的规则合并两个帮派,二者之一成为新的帮主
下面用一个圆圈节点表示一个元素,箭头指向该元素的代表元素,举个例子看看并查集是如何运作的
初始时,有六个元素,每个元素自成一个集合,集合的代表元素当然就是该元素自己。
六个散修各自为战,自成一派
对1号元素和3号元素执行合并操作,两个集合合并,1号成为新集合的代表元素
1号和3号是各自帮派的帮主,直接比武,1号赢了成为合并帮派的新帮主
对2号元素和3号元素执行合并操作,两个集合合并,1号还是新集合的代表元素
3号的帮主1号出来和2号比武又赢了,把2号收为帮众,帮派再次壮大。
4、5、6号元素也进行了上述合并操作,形成一个新的集合,以4号为代表元素
对2号元素和6号元素执行合并操作,
2号和6号把各自的帮主叫出来比武,1号又赢了4号,4号输了认1号为帮主,4号手下的5号和6号也跟着投降了。此时大帮派的帮主是1号,但没有经过组织架构调整,5号和6号还归他们曾经的帮主4号管。
最后,形成了一个大帮派,可以看出这个大帮派的组织架构是树形结构。画成一棵树的形式如下:
这棵树的根节点就是集合的代表元素,要查询某元素所属结合的代表元素只需要一层一层访问父节点直到找到根节点。所以在这棵树中,只有父指针。
并查集由若干棵这样的不相交树构成,也即不相交森林。
也就是说并查集的逻辑结构是树形结构,然而因为只有父指针,在具体实现时,只需要一个数组fa
来存储每个节点中的父节点即可。
下面给出并查集最基础的实现:
1 | class UFS{ |
优化
从上面的实现中,发现Union
操作实际上是两次find
操作和一次赋值操作,那么Union
和find
的时间复杂度是一样的,可以不做区分,统一认为是单次并查集操作。
我们知道树形结构上的操作时间复杂度一般跟树的高度有直接关系。
当并查集中的元素个数为 n
时,上述无优化的并查集的单次操作时间复杂度应为:
平均
最坏
此时是一棵单支树,高度即为节点个数;或者说树退化成了链表
为了提高并查集操作的效率,应尽可能压扁树,即降低树的高度。所以考虑在查询和合并两个操作时,尽可能降低操作后树的高度。
路径压缩
如上图的树形结构,要查询元素2
的根节点,需要一层一层往上,但我们其实是不关心路径上其他节点的,能一步到根是最好的。所以要压缩路径。
如图,把查询路径中所有节点的父节点都设为最终的根节点,下一次查询时就可以直接访问到根节点了。
具体进行路径压缩时,用递归的写法很容易实现上述思路:
1 | int find(int x){ |
加上语法糖简写成一行代码
1 | int find(int x){ |
路径查询的缺点是操作具有滞后性,只能在下一次查询时体现效果;另外,路径压缩可能会破坏树的结构。
按秩合并
路径压缩是在查询时进行,而且只压缩一条路径。所以经过路径压缩之后,并查集的结构可能仍比较复杂。因此我们考虑对合并操作进行优化。
上面在讲合并操作时,始终没提到两棵树合并时是按什么规则合并,简单的并查集中是随机选取一个作为新树的根节点。而这种随机有可能会降低效率。
如上图,此时要合并7
和8
,有两种选择:
如果把7
的父节点设为8
,会使树的高度增大,树中每个元素到根节点的路径都变长了。虽然在后续查询时,可以通过路径压缩降低高度,但是这里多条路径耗费时间且是滞后的,我们可以在合并时就进行优化。
如果把8
的父节点设为7
,就没有这些问题,没有影响其他节点,合并后树的高度也没有增加。这启发我们把简单的树合并到复杂的树上。
也就是按照某种规则决定合并的方向,使得合并后树的高度尽可能小。某种规则也就是秩(rank),用来描述树的复杂程度,通常可以是树的高度、树的节点个数。
用一个rank
数组记录每个节点对应子树的秩。初始化时,每个节点的rank
都是1
;合并时,比较两个节点的rank
大小,把rank
较小的树合并到较大者;更新合并后的rank
。
这里给出以树的节点个数作为秩时,按秩合并的实现:
1 | void Union(int x, int y){ |
以树的高度作为秩也是可行的,需要注意不同高度的树合并后新高度是两者中较大的高度,相同高度的树合并后新高度是原高度+1。
然而考虑到查询时路径压缩会改变树的高度,而且查询时并不会修改rank
,所以合并时的rank
可能并不是准确的高度值。所以一般用的少,这里就不做具体实现了。
其实不准确的高度值并不会影响合并方向的正确性,此时
rank
虽然不是准确的高度值,而是子树高度的上界,这个值是有意义的,也可以描述子树的复杂程度。
完整实现
在查询和合并,我们还可以给并查集添加一些其他操作方便实际使用
获取连通分量(
connected components
)的个数连通分量的个数 = 不相交集合的个数 = 集合代表元素的个数,因此只需要求出代表元素的个数即可。而代表元素的特点是它的代表元素是自己。
1
2
3
4
5
6
7int getCC(){
int cnt = 0;
for(int i=0;i<fa.size();++i){
if(fa[i] == i) cnt++;
}
return cnt;
}跳过冗余边
在合并操作时,如果两个元素已经在同一个集合中也即两个点已经在同一个连通分量中了,那么再对这两个点进行连接就会形成冗余边。在按秩合并时,自己和自己合并会导致
rank
翻倍增加。大量的冗余边会导致并查集的效率降低。因此,在合并前可以判断一下是否是冗余边,若是则直接结束操作以节省时间。
完整代码如下:
1 | class UFS{ |
时间复杂度
优化 | 平均时间复杂度 | 最坏时间复杂度 |
---|---|---|
无优化 | ||
路径压缩 | ||
按秩合并 | ||
路径压缩+按秩合并 |
这里α
表示阿克曼函数的反函数,在宇宙可观测的 n
内(例如宇宙中包含的粒子总数),不会超过5
。
证明非常复杂,感兴趣的可以参考以下论文:
A class of algorithms which require nonlinear time to maintain disjoint sets - ScienceDirect
应用
并查集应用十分灵活,通常用于处理与连通性有关的问题。涉及到集合的合并、点的连通等问题时,就可以考虑使用并查集解决。
解决相关问题时,首先需要在问题中抽象出一个图,确定图中的点集,确定两点的连通关系如何表示。
基于图可以解决以下问题:
- 求无向图的连通分量个数
- 判断无向图中是否有环(求环的个数)、是否有冗余边(求冗余边的条数)
- 利用对连通性的判断,求
kruscal
最小生成树
例题
求连通分量个数
839. 相似字符串组 - 力扣(LeetCode) (leetcode-cn.com)
765. 情侣牵手 - 力扣(LeetCode) (leetcode-cn.com)
求最小生成树
778. 水位上升的泳池中游泳 - 力扣(LeetCode) (leetcode-cn.com)