数据结构学习笔记：不相交集

Author Avatar
Nightn 5月 09, 2017
  • 在其它设备中阅读本文章

不相交集（Disjoint Set）是一种用于解决等价问题的非常有效的数据结构，具有性能优越、实现简单等特点。本文介绍了等价问题、不相交集等概念，并叙述了 Union/Find 算法的实现与优化。

1. 等价关系

等价关系必须满足 3 个条件：

  • 自反性：a 属于 S 集，a 与其本身等价；
  • 对称性：a 等价 b，那么 b 等价 a；
  • 传递性：a 等价 b， b 等价 c，那么 a 等价 c。

如电路连通 是一种等价关系；而 ≥ 不是等价关系，因为它满足自反性和传递性，但不满足对称性。

2. 动态等价问题

问题来了，我们如何用数据结构表示一个等价问题？

最容易想到的是二维数组，N 个元素的集，就需要 N X N 大小的二维数组来存放元素之间的等价关系，虽然这样在访问某两个元素是否等价的时候，通过常数时间即可完成。但我们考虑一个简单的例子，一个存放了 5 个元素的集 {a1, a2, a3, a4, a5}，为了表示这个集中各元素的等价关系，我们就需要构建一个 5 X 5 大小的二维数组，且不说这 O($N^2$) 的空间复杂度，这种表示法很难直接表示出等价关系的传递性，什么意思呢？假如 a1~a2, a3~a4, a5~a1, a4~a2, 根据等价性可以很直观的看出，这个集中的所有元素两两等价，但如果将这种等价关系存储在二维数组中，还能够这么直观的表示出来吗？

2.1 基础知识

在等价问题中，二维数组是不可行的。因此引入等价类的概念。

等价类 ：等价类是全集 S 的一个子集，一个等价类中的所有元素都满足等价关系。

有了等价类的概念，我们不需要再用二维数组表示元素之间是否等价了，而是通过判断两个元素是否属于同一个等价类，来判断它们是否等价。 假设全集 S 中包含 N 个元素，且一开始这 N 个元素相互之间都不等价，即每一个元素都单独属于一个等价类。对于任意等价类 $S_i$ 和 $S_j$，都有 $S_i \bigcap S_j = \emptyset$，因此称整个 S 集为不相交集（Disjoint Set）。不相交集中允许两种运算：Find 和 Union。

  • Find

    Find 接收一个给定的元素，返回该元素所属的等价类的名字。

  • Union

    Union 是添加等价关系，比如添加等价关系 a~b，由等价关系的传递性可知，一旦添加了 a~b，那么 a, b所属等价类的所有元素都满足等价关系。即 a 所属的等价类和 b 所属的等价类合二为一。因此， Union 接收两个元素，首先分别找到这两个元素所属的等价类，若属于同一等价类，即 a 和 b 已经具有等价关系了，那么就不操作；若属于不同等价类，则将两个等价类合并为一个等价类。合并的方式有 Union-by-size 和 Union-by-height (rank) ，具体将在下文展开。

在前文中，我们引入了不相交集中等价类的概念，又介绍了不相交集中的两种运算 Find 和 Union，此外，我们还观察到：

  1. 判断两个元素是否等价，是根据它们是否属于同一个等价类，而不是比较它们的值。我们并不关心元素的值是什么（它仅仅起到区分元素的作用），因此，将不相交集中的所有元素编号 1 到 N，并按需排列。
  2. 等价类的名字不重要，重要的是能够进行比较即可。“等价类1”==“等价类1” 和 “阿猫等价类”==“阿猫等价类” 本质上没有任何区别。

2.2 一维数组

有了上面的基础知识后，是时候考虑用什么样的数据结构来实现不相交集了。首先想到的是一维数组，对于一个包含 N 个元素的不相交集 S，用一个大小为 N 的一维数组表示，数组的下标表示是哪一个元素，而存放的内容是该元素所属的等价类的名称。这样一来，Find 就是根据下标找数组存放的内容，时间复杂度为 $O(1)$，但是将两个等价类进行 Union 的话，则需要遍历整个数组，将对应的等价类名称进行修改，时间复杂度为 $O(N)$。

2.3 单链表

考虑将每一个等价类单独存放在一个链表中，这样一来，Union 就只需要将两个链表合并，Union 的时间复杂度为 $O(1)$，但是每次 Find 的话，就需要遍历所有链表。

3. 最基本的实现

我们将每一个等价类表示为一颗树，树的每个元素有相同的根，根就可以用来命名等价类。树中的每个元素都需要一个父指针，指向其父节点，指向 0 表示该元素就是根。用一维数组来表示不相交集。

#define NumSets 128
typedef int DisjSet[NumSets + 1];
typedef int SetType;
typedef int ElementType;

void Initialize(DisjSet S);
SetType Find(ElementType X, DisjSet S);
void SetUnion(DisjSet S, SetType root1, SetType root2);

//初始化不相交集
void Initialize(DisjSet S){
    for (int i = NumSets; i > 0; i--){
        S[i] = 0;
    }
}

初始化时，另所有的元素都指向 0，即每个元素都是根，并单独构成一棵树。Union 非常简单，只需要把一个树根作为另一个树根的根即可，在此，我们将 root2 连接到 root1 上：

// Stupid
void SetUnion(DisjSet S, SetType root1, SetType root2){
    S[root2] = root1;
}

至于 Find，给定一个元素，每次寻找它的父节点，直到找到该元素的根，即该元素所属的等价类，Find 可以用递归和迭代两种方式实现。

// Find by iteration
SetType Find(ElementType X, DisjSet S){
    while (S[X] > 0){
        X = S[X];
    }
    return X;
}

以上是不相交集的最基本实现。Find 的时间复杂度是 $O(h)$，其中 h 是树的深度，按照上述 Union，最坏情况树的深度会达到 N-1，即最坏情况下，Find 的时间复杂度是 $O(N)$。以下分别从 Union 和 Find 两个角度来改进基本实现。

4. 改进 Union

之前的 Union 非常笨拙，每次都是将 root2 作为 root1 的子树，考虑如下代码：

for (int i = 1; i < NumSets; i++){
        SetUnion(S, Find(i + 1, S), Find(i, S));
    }

通过一系列的 SetUnion，S 变成了一棵深度为 N-1 的树，最坏情况下，单次 Find 的时间复杂度为 $O(N)$。为了优化这一问题，提出 Union-by-size，即不再是简单的将后一棵树连到前一棵树，而是总将尺寸更小的树作为子树。为了追踪树的尺寸（即树包含的元素的个数），不再将树根的值设置为 0，而是将其设置为 -size。同样执行上述 Union 代码，改进前后 Union 对比：

实现代码如下：

//初始化不相交集
void Initialize(DisjSet S){
    for (int i = NumSets; i > 0; i--){
        S[i] = -1; // 初始化为-1，表示一开始每棵树都只有一个元素
    }
}

// Smart Union: Union-by-size
void SetUnion(DisjSet S, SetType root1, SetType root2){
    if (root1 > root2){        //root1作为子树
        S[root2] += S[root1];  //更新父树的size
        S[root1] = root2; 
    }
    else{                      //root2作为子树
        S[root1] += S[root2];  //更新父树的size
        S[root2] = root1;
    }
}

这样一来，所有树的深度都不会超过 $log N$，Find 的时间复杂度为 $O(log N)$ 。

另一种是 Union-by-height，只是对 Union-by-size 的简单修改，每次 Union 都将高度更小的树作为子树，同理，树根存放的是树高 height 的负值，实现代码也比较简单，便不再详述。

5. 改进 Find — 路径压缩

虽然机智地改进了 Union 的算法，但是最坏情况还是很容易发生。一方面，我们还想要进一步优化 Union/Find 算法，另一方面，Union 已经没有改进余地了，那怎么办？当然是改进 Find 了！限制算法性能的最大瓶颈是：在 Union 的过程中，树的平衡性很容易被打破。这样一来，树就很快倾向于最糟糕的情况，既然如此，那我们就在每次 Find 的时候调整树的平衡性，这种聪明的调整叫做路径压缩（Path Compression）。

假如我们执行 Find(X)，路径压缩的效果就是，从 X 到根节点这一路径上的每一个节点，我们都将它的父节点设置为根节点。修改 Find 函数如下：

// Find by recursion with path compression
SetType Find2(ElementType X, DisjSet S){
    if (S[X] <= 0){
        return X;
    }
    else{
        return S[X] = Find(S[X], S);
    }
}

值得注意的是，Path compression 和 Union-by-height 并不兼容，因为路径压缩会改变树的高度，这样导致每次重新计算树的高度都很麻烦，一个解决方案是，不去重新计算它。这样一来，每棵树存储的就不是它实际的高度了，而是估计的高度，我们称之为秩（Rank），这样一来，当你一看到 Union-by-rank ，就知道是怎么一回事了吧。

expand_less