并查集 (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. 储存数据 - 第一部分
我们可以简单地用一个数组 p 记录这个树的森林,数组的大小为 N 个项目,其中 p[i] 记录了项目 i 的父节点,如果 p[i] = i,那么 i 就是这棵树的根,也是包含项目 i 的集合的代表项目。
再次看看上面的可视化,确定这个数组 p 中的值。
讨论:如果 i 是包含它的树的根,我们可以设置 p[i] = -1 而不是 p[i] = i 吗?这有什么影响?
2-3. 含义
[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):创建 N 个项目并用这些 N 个项目形成 M 个不相交的集合。我们随机选择两个不相交的集合并合并它们,直到我们有 M 个随机不相交的集合。由于使用了按秩合并的启发式方法和随机性,初始化过程很不可能创建一个高树。
默认形式是 Initialize(N, N),即 M = N,所有的 p[i] = i 和 rank[i] = 0(所有这些秩值最初都不显示)。这个操作的时间复杂度显然是 O(N)。
由于屏幕大小的限制,我们设置 1 ≤ N ≤ 32。显然 M ≤ N。
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)。如果这是你在这个默认的 UFDS 示例上的第一次调用,它将在 2 步后返回顶点 3,然后由于路径压缩在行动,修改底层的 UFDS 结构(即,顶点 0 直接指向顶点 3)。注意,rank[1] = 1 的 rank 值现在是错误的,因为顶点 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?
Quiz: Starting with N=8 disjoint sets, how short (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?
讨论:为什么?
7-4. 答案
[This is a hidden slide]
8. 实际时间复杂度
到目前为止,我们说FindSet(i),IsSameSet(i, j)和UnionSet(i, j)的运行时间为O(1)。实际上,如果UFDS同时实现了路径压缩和按秩合并启发式,它们的运行时间为O(α(N))。这个分析相当复杂,在这个可视化中被跳过。
这个α(N)被称为阿克曼函数的逆函数,它的增长速度极慢。对于这个UFDS数据结构的实际使用(假设N ≤ 1M),我们有α(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 Network 和Kattis - Control。
请注意,这两个问题都是实际的国际大学生程序设计竞赛(ICPC)问题,也就是说,它们是 "不简单的"。
9-4. 提示
[This is a hidden slide]
9-5. 合并,查找,拆分?
请注意,并查集数据结构没有 "撤销 "操作。一旦两个不相交的集被合并起来,就不容易再把它们分割成原来的两个集,特别是当路径压缩使合并后的树变平时。
讨论:那么,如果我们需要这种 "拆分 "或 "分割 "或 "切割 "的操作,该怎么做呢?
9-6. 答案
[This is a hidden slide]