并查集 (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. 储存数据 - 第一部分

We can simply record this forest of trees with an array p of size N items where p[i] records the parent of item i and if p[i] = i, then i is the root of this tree and also the representative item of the set that contains item i.


Once again, look at the visualization above and determine the values inside this array p.


Discuss: If i is the root of the tree that contains it, can we set p[i] = -1 instead of p[i] = i? What are the implications?

2-3. The Implications

[This is a hidden slide]

2-4. 检查点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-5. 储存数据 - 第二部分

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

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

2-6. 检查点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. Initialize(N, M)

Initialize(N, M): Create N items and form M disjoint sets with these N items. We randomly pick two disjoint sets and merge them until we have M random disjoint sets. Currently this setup is not random enough, i.e., it cannot create tall trees for example.


The default form is Initialize(N, N), i.e., M = N, all with p[i] = i and rank[i] = 0 (all these rank values are initially not shown). The time complexity of this operation is clearly O(N).


Due to the limitation of screen size, we set 1 ≤ N ≤ 16.

5. FindSet(i)

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

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

5-1. 实践案例

If we execute FindSet(12), we will immediately get vertex 12.
If we execute FindSet(9) we will get vertex 6 after 1 step and no other change.


Now try executing FindSet(0). If this is your first call on this default UFDS example, it will return vertex 3 after 2 steps and then modify the underlying UFDS structure due to path-compression in action (that is, vertex 0 points to vertex 3 directly). Notice that rank value of rank[1] = 1 is now wrong as vertex 1 becomes a new leaf. However, we will not bother to update its value.


Notice that the next time you execute FindSet(0) again, it will be (much) faster as the path has been compressed. For now, we assume that FindSet(i) runs in 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): If item i and j come from two disjoint sets initially, we link the representative item of the shorter tree/disjoint set to the representative item of the taller tree/disjoint set (otherwise, we do nothing). This is also done in O(1).


This is union-by-rank heuristic in action and will cause the resulting tree to be relatively short. Only if the two trees are equally tall before union (by comparing their rank values heuristically — note that we are not comparing their actual — the current — heights), then the rank of the resulting tree will increase by one unit.

7-1. 间接路径压缩

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

7-2. 实践案例

On the same default example, try UnionSet(9, 12). As the tree that represents disjoint set {6, 9} is currently taller (according to the value of rank[6] = 1), then the shorter tree that represents disjoint set {12} will be slotted under vertex 6, without increasing the height of the combined tree at all.


On the same default example, try UnionSet(0, 11). Notice that the ranks of vertex 3 and vertex 5 are the same rank[3] = rank[5] = 2. Thus, we can either put vertex 3 under vertex 5 (our implementation) or vertex 5 under vertex 3 (both will increase the resulting height of the combined tree by 1). Notice the indirect path-compression heuristic in action.

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:5
rank:3
rank:2
rank:1
rank:4

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:3
rank:1
rank:4
rank:2
rank:5

讨论:为什么?

7-4. 答案

[This is a hidden slide]

8. 实际时间复杂度

So far, we say that FindSet(i), IsSameSet(i, j), and UnionSet(i, j) runs in O(1). Actually they run in O(α(N)) if the UFDS is implemented with both path-compression and union-by-rank heuristics. The analysis is quite involved and is skipped in this visualization.


This α(N) is called the inverse Ackermann function that grows extremely slowly. For practical usage of this UFDS data structure (assuming N ≤ 1M), we have α(1M) ≈ 1.

9. 附加功能

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

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

9-1. 源代码

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

9-2. 在线测验

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

9-3. 在线评判练习

即使在通过了这个UFDS模块的在线测验后,你认为你已经真正掌握了这种数据结构吗?

让我们来挑战一下你,让你解决两个需要使用并查集的编程问题:UVa 01329 - Corporative NetworkKattis - Control

请注意,这两个问题都是实际的国际大学生程序设计竞赛(ICPC)问题,也就是说,它们是 "不简单的"。

9-4. 提示

[This is a hidden slide]

9-5. 合并,查找,拆分?

请注意,并查集数据结构没有 "撤销 "操作。一旦两个不相交的集被合并起来,就不容易再把它们分割成原来的两个集,特别是当路径压缩使合并后的树变平时。

讨论:那么,如果我们需要这种 "拆分 "或 "分割 "或 "切割 "的操作,该怎么做呢?

9-6. 答案

[This is a hidden slide]