假设八台计算机之间的连线逐一加入。连接 0 与 1,再连接 1 与 2 后,即使 0 与 2 之间没有直接连线,我们也应知道它们属于同一个连通群组。每次新增连线后都重新列出各组全部成员,所做的工作比这个问题真正需要的多。不相交集合结构只记录足以识别及合并群组的信息。
关键是分清哪些元素属于同一组,以及用什么指针表示这件事。查询可以重新整理指针,而不改变任何群组。反过来,一次成功合并可能只改一个父指针,却已改变了群组。始终同时看清这两个层次,算法便较容易证明及调试。
先定义划分与操作
定义 1.1.1
(划分与不相交集合操作)
全集 的一个划分,是一族非空、两两不相交的子集,而它们的并集是 。每个元素因此恰好属于一个子集,称为其集合或分量。
对于 ,初始化时每个元素各自成为单元素集合。find(x) 返回包含 的集合的代表元。如果 x、y 所属集合不同,unite(x,y) 便合并两者。在这个抽象意义下,两个元素连通,恰好等价于当前代表元相等。
例如, 是 的一个划分。它不是图的边列表,而是考虑连通性后所得的群组。关系“属于同一集合”具有自反性、对称性及传递性。
| 操作 | 抽象结果 | 会否改变划分? |
|---|---|---|
find(x) | 所属集合的当前代表元 | 不会 |
connected(x,y) | 代表元是否相等 | 不会 |
unite(x,y) | 是否合并了两个不同集合 | 会,而且恰好在返回真时改变 |
sizeOf(x) | 所属集合的元素数量 | 不会 |
代表元是实现的选择,并非应用程序对象的永久名称。后来的合并可以改变它;尤其不必是集合内最小的元素。
概念视角结构
把合并看成划分的上确界
按细分关系为 的划分排序:若 的每个块都含于 的某个块内,则 。于是 unite(x,y) 把 换成 之上、使 与 同属一块的最小划分。因此,一连串合并之后的划分只取决于合并了哪些配对,与次序及重复无关,虽然父森林确实取决于它们。例如,合并 无论先后都得到 ,但按下文的按大小合并规则(平局时保留标号较小的根),父数组分别是 [0,0,0] 与 [1,1,1]。
用父指针森林表示划分
用数组 parent 存储父指针。根满足 parent[r] == r;其他元素的指针则通向分量的根。除了根指向自己的指针,父边形成没有环的树。由任何元素沿父指针前进,都必须到达唯一的根。两个元素属于同一分量,当且仅当路径到达同一根。
在根上,size[r] 记录整个分量的大小,而不是直接子节点数量,也不是某条可见分支的大小。非根的大小条目不会被当作分量大小使用。起初 parent[x] = x、size[x] = 1,分量数量为 。
例题 1.1.2
(创建森林,不必每次把所有分支展平)
使用八个元素。每次把较小分量接到较大分量之下;大小相等时,保留标号较小的根。由单元素集合开始,依次执行:
| 合并 | 保留的根 | 合并后分量大小 | 剩余分量数量 |
|---|---|---|---|
unite(0,1) | |||
unite(2,3) | |||
unite(0,2) | |||
unite(4,5) | |||
unite(6,7) | |||
unite(4,6) | |||
unite(0,4) |
每次调用连接的是根,并不自动把其他每个节点都改为直接指向保留的根。最后的父指针如下:
| 元素 | ||||||||
|---|---|---|---|---|---|---|---|---|
| 父节点 |
7 的路径是 ,3 的路径则是 。路径长度不同,不表示分量不同:两者都到达 0。当前只有根 0 记录分量大小 8。
路径压缩改变表示,不改变成员归属
find(7) 的第一轮遍历沿三条父边找到根 0。完整路径压缩再把已访问元素改为直接指向该根。7 与 6 的父指针改为 0;4 的条目本来就是 0,数值不变。其他条目维持原状。第二次 find(7) 只需沿 这一条边前进。
以下的寻根步数,只计第一轮沿父边前往根的遍历。不计根指向自己的指针,也不计第二轮压缩;下方实现的压缩阶段还会沿旧路径走一遍。只有前后数值不同,才计作一个已改变的父指针条目。按这些约定,第一次查询寻根走三步、改两项;第二次寻根走一步、不改任何条目。这些计数描述的是此预先创建的例子,并非每次查询都有常数最坏时间的证明。
命题 1.1.3
(路径压缩保持划分)
设 find(x) 把所有经过的元素的父指针改为它找到的根 。改动之后,每个元素的根都与之前相同,所以父森林所表示的划分以及各根上的计数器都没有改变。
证明
(为什么压缩保留每个所表示的集合)
假设已访问元素 原本就到达根 。把其父节点改为 ,不会改变目的地,也不会产生非平凡环: 是根,其路径不会经过某个不同的后代再返回。
其他元素如果原本沿路径到达 ,现在只是用较短的后续路径到达同一根 。完全不经过改写元素的路径则不变。因此,每个元素在压缩前后的根都相同,用根相等所表示的划分完全一致。没有分量增加或失去成员,所以根的大小计数仍正确。
这就解释了为什么 find 可以修改父指针数组,却在抽象层次仍是查询。它改善的是表示方式,没有合并或拆开集合。
并查集:用森林表示一个划分
父指针属于实现细节;元素属于哪个集合才是抽象答案。追踪父指针的遍历与改写,分辨何时森林改变、何时所表示的划分改变。
预先操作(不计入读数):union(0,1)、union(2,3)、union(0,2)、union(4,5)、union(6,7)、union(4,6)、union(0,4)。每次都按分量大小合并;大小相同时选标号较小的根。
找到根后,把每个已访问且尚未直接指向根的元素改为指向该根。关闭此选项仍会按大小合并。
本次追踪的操作: find(7); find(7);
父指针森林
箭头由元素指向其父节点;双圆表示根。下方的父指针与完整路径表提供相同信息。
所表示的划分
{0, 1, 2, 3, 4, 5, 6, 7}
| 元素 | 父节点 | 当前到代表元的路径 | 分量大小(只在根记录) |
|---|---|---|---|
| 0 | 0 (根) | 0 | 8 |
| 1 | 0 | 1 → 0 | — |
| 2 | 0 | 2 → 0 | — |
| 3 | 2 | 3 → 2 → 0 | — |
| 4 | 0 | 4 → 0 | — |
| 5 | 4 | 5 → 4 → 0 | — |
| 6 | 4 | 6 → 4 → 0 | — |
| 7 | 6 | 7 → 6 → 4 → 0 | — |
- 压缩前的遍历路径
- 无
- 第一次查找:父边步数
- 0
- 第二次查找:父边步数
- 0
- 父指针改写次数:压缩
- 0
- 父指针改写次数:合并
- 0
- 集合数量
- 1
- 第一次查找返回
- 尚未返回
- 第二次查找返回
- 尚未返回
步骤 1 / 14
预先建立的森林表示下方的划分。本次追踪尚未执行任何操作;遍历及改写计数均为零。
为何路径压缩保留抽象集合
沿父指针前进,最终会到达父节点为自己的根。两个元素属于同一集合,当且仅当它们的路径到达同一根。已访问元素既然本来就到达根 r,把其父指针改为 r 就不会改变目的地。因此压缩路径不会改变任何元素的集合归属。
合并必须连接根,而非任意元素。两次查找后,把一个根连至另一个不同的根,恰好合并这两个分量,且不会产生环。按大小合并会把较小分量接到较大分量;本例在相等时选较小标号,只影响代表元的选择,不影响数学上的集合合并。
若不压缩,每次元素深度增加,都是因为其分量被接到一个至少同样大的分量,所以包含它的分量大小至少倍增。故深度不超过 floor(log₂ n)。压缩不会增加深度。此处 n=8,单次查找最多沿三条父边。本小示例的计数不足以证明更强的一般摊还时间界。
一步是沿一条父边前进,不计根指向自己的边。改写只计父指针的值确实改变。大小计数的写入、预先操作、图形排位及读取表格均不计入。根的大小是整个分量的大小;非根的破折号不表示空集合。
阅读完整追踪
- 预先建立的森林表示下方的划分。本次追踪尚未执行任何操作;遍历及改写计数均为零。
- 第 1 次查找从元素 7 开始。
- 7 → 6. 沿此父边前进,计一步。父指针数组不变。
- 6 → 4. 沿此父边前进,计一步。父指针数组不变。
- 4 → 0. 沿此父边前进,计一步。父指针数组不变。
- parent[0] = 0. 此元素的父节点就是自己,因此它是代表元。其大小计数记录整个分量,而非单一分支。
- parent[7]: 6 → 0. 把此父指针改为指向已找到的根。一个父指针的值改变,但代表元与集合成员都不变。
- parent[6]: 4 → 0. 把此父指针改为指向已找到的根。一个父指针的值改变,但代表元与集合成员都不变。
- 本次查找返回 0.
- 第 2 次查找从元素 7 开始。
- 7 → 0. 沿此父边前进,计一步。父指针数组不变。
- parent[0] = 0. 此元素的父节点就是自己,因此它是代表元。其大小计数记录整个分量,而非单一分支。
- 本次查找返回 0.
- 两次查找返回同一代表元。比较父边步数:第二条路径缩短是之前压缩的效果,并非最坏时间为常数的证明。
八个固定元素,按大小合并,结果可复现。重复查找模式执行两次 find(x);合并模式先执行 find(x)、find(y),再决定是否连接根。本图不会向外保存数据或发送请求。
一起实现连接根与路径压缩
以下完整 C++ 例子假设 ,每次操作都接收 内的已有标号。类只在创建时产生单元素集合;之后支持合并,不支持删除元素或分开分量。
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
class DisjointSet {
std::vector<int> parent, size;
int components;
public:
explicit DisjointSet(int n) : parent(n), size(n, 1), components(n) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (parent[x] != x) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
bool unite(int x, int y) {
int a = find(x), b = find(y);
if (a == b) return false;
if (size[a] < size[b] || (size[a] == size[b] && a > b)) {
std::swap(a, b);
}
parent[b] = a;
size[a] += size[b];
size[b] = 0;
--components;
return true;
}
bool connected(int x, int y) { return find(x) == find(y); }
int sizeOf(int x) { return size[find(x)]; }
int count() const { return components; }
};
int main() {
DisjointSet sets(8);
for (auto edge : std::vector<std::pair<int, int>>{
{0, 1}, {2, 3}, {0, 2}, {4, 5}, {6, 7}, {4, 6}, {0, 4}}) {
sets.unite(edge.first, edge.second);
}
std::cout << sets.find(7) << ' ' << sets.count() << ' '
<< sets.sizeOf(7) << '\n';
}
输出是 0 1 8:代表元为 0,只有一个分量,内有八个成员。在 find 中,先用 next 保存旧父节点,再覆写指针;否则第二轮遍历会失去原路径。把原本已等于 root 的父指针再次赋值并无问题,但不属于前述数值有改变的事件。
在 unite 中,比较大小前,a 与 b 都是根。连接两个不同的根,恰好合并两棵树,也不会产生环,因为两根原本属于不同树。合计大小并把分量数减一,便记录了这次成功合并。清空 size[b] 是标示该计数已过时;sizeOf 只读取根上的条目。
如果两次查找返回同一根,方法返回假,划分与分量数量不变。不过,在作出决定前,两次查找仍可能已压缩路径。“没有新的合并”不等于“没有写入任何父指针”。
例题 1.1.4
(多余的合并仍会写入父指针)
从上面的父数组 [0,0,0,2,0,4,4,6] 出发,调用 unite(7,4)。find(7) 走过 ,共三步,并把 parent[7] 与 parent[6] 改为 0;parent[4] 本来就是 0。find(4) 走一步。两个根都是 0,所以 unite 返回 false,分量数仍是 1,size[0] 仍是 8。数组却已变成 [0,0,0,2,0,4,0,0]。没有发生合并,但父指针被写入了。
常见错误
(比较父指针而不是比较根)
在 [0,0,0,2,0,4,4,6] 中,parent[3]=2、parent[1]=0,两者不相等,但 1 与 3 属于同一分量。连通测试必须比较 find(1) 与 find(3),两者都等于 0。
常见错误
(在非根元素上读取大小计数器)
实现在连接时会清除被连接的根的计数器:unite(2,3) 之后,size[3] 为 0,然而 3 所在的分量有 8 个元素。分量大小必须用 sizeOf(3) 读取,即 size[find(3)]。
反例模式
随意改一个父指针,可以拆散旧集合
假设 parent = [0, 0, 1, 3],它表示 及 。错误的 unite(2,3) 实现如果直接指定 parent[2] = 3,新的根便表示 及 。2 被从旧伙伴中拆走,并没有把两个完整集合合并。
应先找到根 0 与 3,再把一个根连到另一个之下。按所示实现,查找 2 先把其父指针压缩为 0;大小规则再把 3 接到 0,得到 [0, 0, 0, 0] 及一个集合 。旧成员仍到达相同根,关系没有失去。不相交集合合并的是整个等价类;不能只因参数给了非根元素,就拆散原有类。
用倍增证明深度上界
定理 1.1.5
(按大小合并限制深度)
设每次合并都把较小分量的根连到另一个分量的根之下,大小相等时任选其一。则在含 个元素的全集中,每个元素的深度至多为 ,所以每次 find 需时 。
证明
(按大小合并限制深度增加的次数)
先考虑没有路径压缩的合并。只有当某元素所属分量的根被接到另一个根之下,该元素深度才增加一。如果原分量大小为 ,大小规则保证它接到大小至少为 的分量。因此,新分量大小至少是 。
由单元素集合开始,经过 次这种深度增加,所属分量至少有 个元素。全集只有 个元素,所以对于 有
因此,沿路径找到根需要 时间。压缩只会缩短路径,故不会使这个上界失效。两轮 find 的时间,至多是所走路径长度的常数倍;一次合并则作两次这样的查找,再作固定数量的额外工作。
八元素例子在压缩前,元素 7 的深度达到三,恰好是 。重复查询已压缩的路径可以便宜得多。要分析多次操作更精细的摊还成本,仍需要另一个论证,不能只看见第二条路径较短便下结论。
证明透视
为什么按大小合并能使分量大小翻倍
整个证明只依靠一个不等式:被连接的那棵树不比接收它的树大,所以被连接的元素落入的分量,大小至少是原来的两倍。它只作用于被连接那棵树的元素;接收的树中元素的深度不变。路径压缩只用一句话处理:它只会降低深度,因此即使部分路径已被缩短,深度也不会超过深度增加的次数。
这条规则不能去掉。如果 unite(x,y) 总是把 所在集合的根连到 所在集合的根之下,那么依次调用 unite(0,1)、unite(1,2)、、unite(n-2,n-1) 会建成链 ,而 find(0) 需要走过 条边。
初始化需要 时间,两个数组占用 空间。要说明完整操作的成本:已知根之后,连接根只需常数工作;unite(x,y) 却必须先把根找出来。
应用到逐步加入边的连通性
固定顶点集合,由没有边及各自独立的单元素集合开始。每当无向边 加入,调用 unite(u,v)。
定理 1.1.6
(并查集追踪逐步加入边后的连通性)
按此过程,每处理完一条边之后,两个顶点的代表元相等,当且仅当已处理的边能用路径连接它们。
证明
(每条边不是连接两个分量,就是留在同一分量内)
起初,不同顶点之间没有这种路径。加入一条边,可能连接两个原有连通分量,也可能留在同一分量内。合并操作恰好作出相同区分,因此每次加入边后都保留不变量。
这证明 connected(u,v) 能回答当前是否连通,却不会找出图内的实际路径。父边是实现指针,不一定是输入图的边。
在简单无向图中,如果一条边的端点原本已连通,它会与原有路径形成环。因此,不相交集合可用于 Kruskal 的环检查:按权重非递减次序处理边,端点属于不同集合时才接纳。数据结构实现的是这项检查;要证明所得为最小生成树,还需要贪心法的割性质论证,与并查集不变量是不同部分。
例题 1.1.7
(逐条边判断接受还是拒绝)
取顶点 ,各自为单元素集合,按顺序处理边 ,使用上面的实现,大小相等时保留标号较小的根。
| 边 | 两个根 | 结果 | 之后的分量数 |
|---|---|---|---|
| 接受:1 连到 0 之下 | |||
| 接受:2 连到 0 之下 | |||
| 拒绝:已在同一集合 | |||
| 接受:4 连到 3 之下 | |||
| 接受:3(大小 2)连到 0(大小 3)之下 | |||
拒绝:find(4) 沿 走,并把 parent[4] 设为 0 |
接受了 4 条边,恰为 ,被拒绝的两条边就是会形成环的边。被拒绝的边 的两端在父森林中并不相邻,却已被先前接受的边连通。最后的父数组是 [0,0,0,0,0]。
反例模式
只靠划分,不能处理任意删边
路径图的边为 ;三角形的边为 。两者都得到划分 。现在各自删除 :路径图分成 与 ,三角形却仍可经过 0 连通。
同一个已存储划分及同一项删除,竟需要不同答案,因为划分已丢失哪些替代路径存在的信息。普通并查集不能只把某个父指针赋值反转,便解决任意删边。含删除的问题需要额外信息或另一个算法,不能无依据地在这个接口加上拆分操作。
练习
快速检查
(1. 分清查询的指针改变与答案)
从上面的八元素父指针表开始,尚未作任何压缩。连续执行两次 find(3)。写出每次寻根步数、数值有改变的父指针条目、返回代表元,以及最后的分量数量。
解答 · 解答 1
第一次路径是 ,共两步,只把 parent[3] 由 2 改为 0。第二次路径是 ,一步,不改任何条目。两次都返回 0,仍只有一个分量。其他分支,包括由 7 出发的路径,都没有被这两次调用压缩。
快速检查
(2. 成功合并不一定展平新分量)
改由 parent = [0,0,0,2,4,4,4,6] 开始,其中有两个大小为四的分量,根为 0 及 4。启用压缩,执行所实现的 unite(3,7)。最后父指针数组是什么?下一次 find(7) 在压缩前会走什么路径?
解答 · 解答 2
查找 3 把其父指针改为 0。查找 7 沿 前进,把其父指针改为 4。大小相等,故把根 4 接到根 0 之下。最后数组是 [0,0,0,0,0,4,4,4],下一次由 7 出发的路径是 ,共两步。连接根 4,并没有自动把它的所有子节点都改为直接指向 0。
快速检查
(3. 判断代表元是否必须为最小标号)
一个分量的成员是 ,根为 0;另一个分量的成员是 ,根为 4。按大小合并时,哪个根保留?标号较小者优先的平局规则会改变决定吗?
解答 · 解答 3
保留根 4,因为其分量大小为六,大于二。大小不同,平局规则不适用。所得集合包含 0,代表元却是 4。比较代表元仍可正确识别分量;选最小标号并非这个结构的抽象契约。
快速检查
(4. 分清连接根与完整合并的成本)
全集有九个元素并采用按大小合并。按倍增证明,父指针路径可以有深度四吗?为什么只因操作改一个根指针,就把整个 unite(x,y) 称为常数时间,并不完整?
解答 · 解答 4
深度四至少需要 个元素,所以按这些规则, 时不可能;上界是 。两根已知时,连接它们只需常数工作,但发现两根需要两次查找。对数上界同时考虑了这些遍历、压缩阶段及最后的连接。