Skip to content

第五章 - 不相交集 ADT

约 2252 个字 3 行代码 预计阅读时间 8 分钟

等价关系

若对于每一对元素 \((a, b)\)，\(a, b \in S\)，\(aRb\) 为 true 或 false，则称在集合 \(S\) 上定义关系 (relation) \(R\)。若 \(aRb\) 为 true，则称 \(a\) 与 \(b\) 有关系。

等价关系 (equivalence relation) 是满足下列三个性质的关系 \(R\)：

  1. 自反性 (reflexivity)：对于所有的 \(a \in S\)，\(aRa\)。
  2. 对称性 (symmetry)：\(aRb\) 当且仅当 \(bRa\)。
  3. 传递性 (transitivity)：若 \(aRb\) 且 \(bRc\)，则 \(aRc\)。

动态等价性问题

等价类

一个元素 \(a \in S\) 的等价类 (equivalence class) 是 \(S\) 的一个子集，它包含所有与 \(a\) 有关系的元素。所有等价类形成对 \(S\) 的一个划分，即 \(S\) 的每一个元素恰好出现在一个等价类中。因此为确定是否 \(aRb\)，我们只需验证 \(a\) 和 \(b\) 是否在同一个等价类中。

问题描述

具体地，我们来解决这样一个问题，即动态等价性问题。

假设输入数据最初是 \(N\) 个集合的类 (collection)，每个集合含有一个元素。初始的描述是所有关系除自反外均为 false。每个集合都有一个不同的元素，从而 \(S_{i} \cap S_{j} = \varnothing\)，因此这些集合是不相交 (disjoint)。

此时有两种运算允许进行。第一种运算是 Find，它反包含给定元素的集合（即等价类）的名字。第二种运算是添加关系，如果想要添加关系 \(aRb\)，先对 \(a\) 和 \(b\) 进行 Find，若两者已经在同一个等价类中则无限续额外操作，否则使用求并运算 Union，将含有 \(a\) 和 \(b\) 的两个等价类合并成一个新的等价类。从集合的观点来看，\(\cup\) 的结果是建立一个新集合 \(S_{k} = S_{i} \cup S_{j}\)，去掉原来两个集合而保持与其它集合的不相交性。这项算法即称不相交集合的 Union/Find 算法。

这种算法是动态的 (dynamic)，因为在算法执行的过程中，其执行对象（即集合）会通过 Union 运算发生改变。这种算法也是联机 (on-line) 操作，当 Find 执行时，其必须返回结果后算法才能继续考察下一个问题。

Note

相对地，另一类算法称作脱机 (off-line) 操作。这类算法在输入所有问题后再依次返回结果。

对于这个问题，我们可以注意到两点。第一，我们不需要进行比较元素值的操作，而只需要知道它们的位置，因此只需将各元素按 \(1\) 到 \(N\) 顺次编号，并定义初始的不相交集合 \(S_{i} = \{i\}\)。第二，我们也不需要特别关注在若干次 Union 操作后元素具体在哪个集合中，只需要知道 \(\texttt{Find}(a) = \texttt{Find}(b)\) 当且仅当 \(a\) 和 \(b\) 在同一个集合中。

解决方案

解决动态等价问题的方案有两种。

一种方案是储存每个元素的等价类。这种方案下的 Find 操作显然是 \(O(1)\) 的，但 Union 操作需要遍历被合并元素的等价类中的所有元素，最后达到 \(\Theta (N^{2})\) 的复杂度。

这种方案往往难以采用，因为两种操作的平均复杂度太高了。因此在后文中我们将着重讨论另一种方案，该方案的 Union 操作的时间复杂度低而 Find 操作的时间复杂度较高，但平均复杂度能到接近常数的水平。

Note

研究表明，同时使得 Find 和 Union 操作达到常数复杂度的算法是不存在的。

基本数据结构

鉴于我们不要求 Find 操作返回任何特定的内容，只要求当且仅当两个元素属于相同的集合时，作用在这两个元素上的 Find 返回相同的名字。我们可以想到用树来表示每一个集合，因为树上的每一个元素都有相同的根。

我们用树来表示每个集合（这些树的集合构成一个森林 (forest)），开始时每个集合只有一个元素。由于我们对这些树的形态没有任何要求，因此我们只需要用记录每个节点的父节点。更具体地，我们只需要用一个数组 P[i] 表示元素 i 的父节点。如果 i 是根，则 P[i]=0。

我们以含有 8 个节点的情况为例，下图即为初状态：

为执行两个集合的 Union 操作，我们只需将一个节点的父指针指向另一棵树的根节点。显然这种操作花费常数时间。一般地，我们规定 Union(X, Y) 后新的根为 X。

沿用前例，在执行 Union(5, 6)、Union(7, 8)、Union(5, 7) 后的森林如下图：

Find 操作只需采用递归的方法返回元素所在树的根即可，显然该操作的时间复杂度与元素所在节点的深度成正比。

事实上，这种算法的最坏时间复杂度可能达到 \(O(MN)\)，容易想到这也是树的结构退化所导致的。而这一复杂度一般是不可接受的，因此我们将讨论几种优化方法。

灵巧求并算法

在原始算法中，对 Union 的执行是相对任意的，即总是让第二棵树成为第一棵树的子树。因此如果我们能在 Union 的具体实现上有所改进，使得树的结构尽量不退化，那我们或许就能得到更高效的算法。

按大小求并

第一种方法称作按大小求并 (union-by-size)，即在执行 Union 操作时，总是让较小的树成为较大的树。

可以证明，通过按大小求并执行 Union 操作，那么任何节点的深度均不会超过 \(\log N\)，这样我们的最坏时间复杂度仅为 \(O(M \log N)\)。

当然，这种改进并非毫无代价的，我们需要额外记录每一棵树的大小，而这一大小需要在每次 Union 操作后修改。但总的来说，这一改进的效果仍然是显著的。

按高度求并

另一种方法称作按高度求并 (union-by-height)，也称按秩 (rank) 求并，即在执行 Union 操作时，总是让深度较浅的树成为深度较深的树。

可以发现，这种方法只是按大小合并的简单修改，其同样保证所有树的深度最多是 \(O(\log N)\)。

路径压缩

上述两种改进方法都是优化了 Union 操作，其最坏情形仍然为 \(O(M \log N)\)。因此我们不妨转换思路，试图对 Find 操作做一些改进，以达到更好的效率。

一个广为认可的改进称作路径压缩 (path compression)，其只与 Find 操作有关。具体来说，路径压缩的效果是，在执行 Find(X) 操作时，对于 X 根节点的路径上的每一个节点，将其父节点变为根节点。

路径压缩的代码实现是非常简洁优美的。这一点在笔者学习算法竞赛期间就留下了深刻的印象，因此希望在这里特别展示：

SetType Find (ElementType X, DisjSet S) {
    return S[X] <= 0 ? X : S[X] = Find(S[X], S);
}

一个自然的想法是，能否同时采用对 Union 的改进和对 Find 的改进。容易发现，路径压缩和按大小求并是可以兼容的，而与按高度求并并不兼容，因为我们路径压缩会改变树的高度。因此接下来我们将讨论这些改进方法的具体时间复杂度。

按秩求并和路径压缩的最坏情形

与这两种算法的简洁性不同，对其时间复杂度的研究即证明一直是学界积极研讨且难以用简单方法证明的。这里我们直接给出结论，具体的证明和分析方法供感兴趣的读者自行研究。

两种算法的时间复杂度均为 \(\Theta (M \alpha (M, N))\)，其中 \(\alpha (M, N)\) 称作反 Ackermann 函数，即 Ackermann 函数的逆。

Ackermann 函数定义如下：

  • \(A(1, j) = 2^{j}, j \geq 1\)
  • \(A(i, 1) = A(i - 1, 2), i \geq 2\)
  • \(A(i, j) = A(i - 1, A(i, j - 1)), i, j \geq 2\)

故反 Ackermann 函数定义如下：

\[\alpha(M, N) = \min \{i \geq 1 | A(i, \lfloor \frac{M}{N} \rfloor) > \log N\}\]

可以看出这一函数是由递归定义的，读者无需掌握有关其更多的数学性质，只需了解其增长极快。具体地，\(A(2, 4) = 2^{65536} - 3\)。因此在实际情况下，将 \(\alpha(M, N)\) 取为 \(4\) 基本是合理的。

由此我们进一步表明，同时采用多种优化算法是不太必要的，因为任何单独一种优化算法都已经得到了非常好的时间复杂度。