并查集 (Union-Find Disjoint Sets, 简称UFDS)

1. Introduction

并查集(UFDS)数据结构被用来模拟多个不相交集,它能够有效率地(即在几乎常数的时间内)确定一个元素属于哪个集,测试两个元素是否属于同一个集,并在需要时将两个不相交集合并为一个。它可以用来寻找无向图中的连接分量,因此可以作为最小生成树(MST)问题的Kruskal算法的一部分。

2. 可视化

在此查看并查集可视化的例子!
每棵树代表一个不相交的集合(因此多个不相交集合能形成一个森林),树的根是这个不相交集合的代表项目。

现在停下来看看当前可视化中的树。 总共有多少项(N)? 有多少个不相交的集合? 每个不相交集的成员是什么? 每个不相交集的代表项是什么?

2-1. 检查点1

由于我们固定了这个电子讲座的默认例子,你的答案应该是。N=13,有4个不相交的集合。{0,1,2,3,4,10}, {5,7,8,11}, {6,9}, {12},下划线的成员是他们自己不相交集合的代表项。

2-2. 储存数据 - 第一部分

我们可以简单地用一个大小为N项的数组p来记录这个树的森林,其中p[i]记录了第i项的父项,如果p[i]=i,那么i就是这个树的根,也是包含第i项的集合的代表项。

再次看一下上面的可视化图,确定这个数组p里面的值。

2-3. 检查点2

在同一个固定的例子上,你的答案应该是p=[1,3,3,3,5,6,5,5,6,4,8,12],大小N=13,范围从p[0]到p[12]

你可以检查一下,p[3]=3,p[5]=5,p[6]=6,p[12]=12,这与{3,5,6,12}是(它们自己的不相交集)代表项的事实一致。

2-4. 储存数据 - 第二部分

我们还在同样大小为N的数组rank中记录额外的等级信息。rank[i]的值是根植于顶点i的子树高度的上限,它将被用作UnionSet(i, j)操作的启发式指导。你会注意到,在 "路径压缩 "(将在后面描述)压缩某些路径后,rank值不再反映该子树的真实高度。

由于有很多项的等级为0,我们对可视化进行了如下设置,以减少杂乱:只有当顶点i的等级大于0时,VisuAlgo才会在顶点i下面以红色文字显示rank[i]的值(简写为一个字符r)。

2-5. 检查点3

在同一个固定的例子上,验证{1,4,6,8}的等级为1,{3,5}的等级为2,其余的等级为0(未显示)。

在这个时间点上,所有的等级值都是正确的,也就是说,它们确实描述了根在该顶点的子树的高度。我们很快就会看到,在接下来的几张幻灯片中,它们并不总是正确的。

3. 操作

此可视化页面中有五个可用的合并集操作:
示例,Initialize(N)(初始化),FindSet(i)(查找),IsSameSet(i,j)(在同一集),和UnionSet(i,j)(合并)
第一个操作(示例)并不重要:具有各种特殊特征的合并集结构实例列表,供您参考。 此e-Lecture模式始终使用“四个不相交集(Four disjoint sets)”示例作为起点。
另请注意,没有一个例子包含 "非常高 "的树。 在我们描述了所使用的两种启发式方法之后,你很快就会明白其中的原因。

4. 初始化(N)

Initialise(N):创建N个不相交集,所有这些都具有p [i] = i rank[i] = 0(这些等级值最初未示出)。
该操作的时间复杂度非常明显是O(N)。
由于屏幕尺寸的限制,我们设置1≤N≤16。

5. FindSet(i)

FindSet(i):从顶点i,递归地在树上往上移动。 也就是说,从顶点i,我们转到顶点p [i]),直到我们找到该树的根,这是该不相交集的的代表项(代表项具有p [i] = i的性质)。

在这个FindSet(i)操作中,我们在每次调用FindSet(i)之后使用路径压缩,因为现在沿着从顶点i到根的路径的每个顶点都知道根是它们的代表项,并且可以用O(1)时间直接指向它 。

5-1. 实践案例

如果我们执行FindSet(12),我们将立即得到顶点12。如果我们执行FindSet(9),我们将在1步之后得到顶点6,并且没有其他变化。

现在试着执行FindSet(0)。如果这是你对这个默认的并查集例子的第一次调用,它将在2步后返回顶点3,然后由于路径压缩的作用而修改其内部结构(也就是说,顶点0直接指向顶点3)。注意,rank[1]=1的等级值现在是错误的,因为顶点1变成了一个新的叶顶点。然而,我们不会费心去更新它的值。

注意,下次再执行FindSet(0)时,由于路径已经被压缩,速度会快很多。现在,我们假设FindSet(i)的运行速度为O(1)。

6. IsSameSet(i, j)

IsSameSet(i,j):只需检查是否 FindSet(i) == FindSet(j)。 该函数经常出现在Kruskal的MST算法中。 由于它只调用FindSet操作两次,我们假设它的时间复杂度为O(1)。

请注意,FindSet函数在IsSameSet函数内部被调用,因此也间接使用了路径压缩

6-1. 实践案例

如果我们调用IsSameSet(3, 5),我们应该得到false,因为顶点3和顶点5是它们各自不相交集合的代表项,它们是不同的。

现在在相同的默认例子上尝试IsSameSet(0, 11),看看顶点0和顶点11的间接路径压缩。我们应该得到false,因为两个代表项:顶点3和顶点5,是不同的。注意,现在顶点{1,5,8}的等级值是错误的。但我们不会修复它们。

7. UnionSet(i, j)

UnionSet(i, j):如果i和j项最初来自两个不相交的集合,我们将较短的树/集合的代表项链接到较高的树/集合的代表项(否则,我们不做任何事情)。这也是在O(1)中完成的。

这就是按等级启发式合并的作用,它将导致产生的树高度相对较短。只有当两棵树在并合前是一样高的(通过启发式比较它们的等级值--注意我们不是在比较它们的实际高度),那么结果树的等级将增加一个单位。

7-1. 间接路径压缩

还要注意的是,UnionSet函数中调用了FindSet函数,所以路径压缩也被间接使用。每次路径压缩压缩路径时,至少有一个等级值是不正确的。我们不需要去修正这些等级值,因为它们只是作为UnionSet函数的指导性启发。

7-2. 实践案例

在同样的默认例子中,尝试UnionSet(9, 12)。由于代表集{6, 9}的树目前比较高(根据rank[6] = 1的值),那么代表集{12}的较短的树将在顶点6下归位,而完全不增加合并后树的高度。
在同样的默认例子中,尝试UnionSet(0, 11)。注意,顶点3和顶点5的等级是相同的 rank[3] = rank[5] = 2。因此,我们可以把顶点3放在顶点5下面(我们的实现),或者把顶点5放在顶点3下面(两种选择都会使合并后树的结果高度增加1)。注意这里间接路径压缩的作用。

7-3. 小测验

Quiz: Starting with N=8 disjoint sets, how tall (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?

rank:1
rank:4
rank:5
rank:2
rank:3

Quiz: Starting with N=8 disjoint sets, how short (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?

rank:5
rank:4
rank:1
rank:2
rank:3

讨论:为什么?

7-4. 答案

[This is a hidden slide]

8. 实际时间复杂度

到目前为止,我们说 FindSet(i), IsSameSet(i, j), 和 UnionSet(i, j) 的运行速度为O(1). 实际上,如果UFDS同时采用路径压缩和启发式按等级合并的方法来实现,它们的运行速度为 O(α(N)) 。


这个α(N) 被称为反Ackermann函数,增长速度极慢。对于这种UFDS数据结构的实际使用 (假设 N ≤ 1000000), 我们有 α(1000000) ≈ 1.

9. 附加功能

您已经完成了这个并查集数据结构的基本内容,我们鼓励您进入探索模式,用您自己的例子探索这个简单而有趣的数据结构。

然而,我们还有一些更有趣的并查集挑战给你。

9-1. 源代码

请看以下C++/Python/Java/OCaml实现的面向对象编程(OOP)方式并查集实现:unionfind_ds.cpp | py | java | ml
你可以根据自己的需要自由地定制这个实现,因为一些较难的问题需要对这个基本实现进行定制。
我确实希望有一天C++/Python/Java/OCaml/其他编程语言能将这种有趣的数据结构纳入他们的基础库。

9-2. 在线测验

关于这个数据结构的一些更有趣的问题,请在并查集训练模块 上练习。