算导并查集笔记

  • 算法导论并查集部分笔记

CLRS 上面称它为“用于不相交集合的数据结构”。(第 21 章)

基本操作

我们要找一个 disjoint-set data structure 维护一个不相交动态集的集合。每个集合有一个代表元。在很多应用中,我们不关心哪个成员被用来代表,只关心动态集合的代表不应当在动态集合没有修改的时候发生变化。

当然,这个代表元并非随便选取,可能有时会有某种规则(比如选取最小的元素)

我们希望支持以下三中操作:

MAKE-SET(x):建立一个新的集合。
UNION(x, y):合并包含 x 和 y 的两个动态集合。
FIND-SET(x):返回一个指针,指向包含 x 的集合的代表。

不难发现,这样的数据结构可以用来快速维护一个无向图的连通分量。

链表表示

每个集合的对象包含 head 属性和 tail 属性, head 属性指向表的第一个对象, tail 属性指向最后一个对象。链表中的每个对象都包含一个集合成员。

在这种表示法中,UNION 操作的耗时最多,对于每个对象,我们必须更新指向集合对象的指针,这与所在链表长度呈线性关系。

事实上,一个 UNION 操作的摊还时间为 $\Theta(n)$

加权合并启发式策略:如果两个集合都有 $\Omega(n)$ 个成员,则单个的 UNION 操作仍需要 $\Omega(n)$ 时间。而一个具有 m 个操作(三种一共)的操作序列,使用启发式合并,需要的时间为 $O(m + nlogn)$。

由于每个 UNION 操作合并两个不相交集,因此至多执行 $n-1$ 次 UNION 操作。我们知道对于任意的 $k \leq n$,在 x 的指针被更新 $\lceil logk \rceil$ 次之后,结果集合一定至少有 k 个成员。因为最大集合至多包含 n 个成员,故每个对象的指针在所有的 UNION 操作中最多被更新 $\lceil logn \rceil$ 次。因此在所有的 UNION 操作中被更新的对象的指针总数为 $O(nlogn)$。

不相交集合森林

考虑更快的实现。我们用有根树来表示集合,树中每个结点包含一个成员,每棵树代表一个集合,在一个不相交集合森林中,每个成员仅指向父结点。每棵树的根包含集合的代表,且其为自己的父结点。
在之前的实现中,一个包含 $n-1$ 个 UNION 操作的序列可以构造出一个恰好有 n 个结点的线性链的树。我们需要使用下面两个 trick 来得到一个渐进最优的不相交集合数据结构。
这两种做法都是能改进运行时间的启发式策略。

按秩合并

类似上面链表中的加权合并启发式策略,每次使具有较少结点的树的根指向具有较多节点的树的根。算导中表示并不需要显式地记录每个结点为根的子树的大小,而是采用一种“易于分析”的方法。对于每个结点,维护一个,它表示该结点高度的一个上界。在使用按秩合并的时候,我们让具有较小秩的根指向具有较大秩的根。

路径压缩

在 FIND-SET 的时候,让查找路径的每个结点直接指向根。路径压缩并不改变任何结点的秩。

启发式策略对运行时间的影响

如果单独使用按秩合并或者路径压缩,他们每一个都能改善不相交集合森林上操作的运行时间。
单独按秩合并:$O(mlogn)$,且上界是紧的。
单独路径压缩:$\Omega(n+f \times (1+log_{2+f/n}n))$
然而只有一起使用的时候最坏情况运行时间为 $O(m\alpha(n))$,这里 $\alpha(n)$ 是阿克曼函数的反函数。

按秩合并+路径压缩的分析

证明太硬核了…… 我要跳过它

思考题

脱机最小值

1
2
3
4
5
6
7
8
OFF-LINE-MINIMUM(m, n)
for i = 1 to n
determine j such that i in K[j]
if j != m + 1
extracted[j] = i
let l be the smallest value greater than j for which set K[l] exists
K[l] = K[j] ∪ K[l], destroying K[j]
return extracted