526互联

算法导论-第21章-用于不相交集合的数据结构

发布时间 2023-06-29 21:50:37作者: gengduc

21.1节描述不相交集合数据结构支持的各种操作，并给出一个简单的应用。21.2节使用一种简单链表结构来实现不相交集合。21.3节使用有根树来实现，使用树表示的运行时间理论上好于线性时间，然而对于所有的实际应用它确是线性的。

21.1 不相交集合的操作

一个不相交集合数据结构（disjoint-set data structure）维护了一组不相交动态集的集合 \(sets = \{S_1, S_2, \cdots, S_k\}\)。用集合中的某个成员作为代表（representative）来标识集合。在一些应用中，我们并不关心选择哪个元素作为集合的代表，只要求在集合没有被修改的情况下每次访问代表得到的答案是相同的。在另外一些应用中，我们需要按照预先设定的规则选择每个集合的代表，比如选择每个集合中关键字最小的元素作为代表。

设 \(x\) 为一个对象，对一个不相交集合数据结构的操作如下：

  • MAKE-SET(x)：建立一个新的集合，它的唯一成员是 \(x\)。因为各个集合是不相交的，故 \(x\) 不会出现在别的集合中。
  • UNION(x， y)：将包含 \(x\) 和 \(y\) 的两个动态集合（表示为 \(S_x\) 和 \(S_y\)）合并成一个新的集合，即两个集合的并集。假定在操作之前这两个集合是不相交的。虽然UNION的很多实现中选择 \(S_x\) 或 \(S_y\) 中的代表作为新集合的代表，实际上新集合的代表可以是 \(S_x \cup S_y\) 中的任何成员。由于我们要求各个集合不相交，故要将 \(S_x\) 和 \(S_y\) 从 \(sets\) 中删除。实际上，通常将一个集合并入另一个集合来代替删除操作。
  • FIND-SET(x)：返回一个指针，指向包含 \(x\) 的（唯一）集合的代表。

本章用两个参数分析不相交集合数据结构的操作的运行时间。 \(n\) 表示执行MAKE-SET操作的次数， \(m\) 表示执行MAKE-SET、UNION和FIND-SET操作的总次数。因为各个集合是不相交的，所以每个UNION操作减少一个集合。因此，最多执行 \(n-1\) 次UNION操作。由于MAKE-SET操作包含在总操作次数中，因此有 \(m \ge n\)。这里我们假设 \(n\) 个MAKE-SET操作总是最先执行的 \(n\) 个操作。

不相交集合的一个应用----确定无向图的连通分量

不相交集合数据结构的应用之一就是确定一个无向图的连通分量。

过程CONNECTED-COMPONENTS使用不相交集合操作来计算一个图的连通分量，一旦过程CONNECTED-COMPONENTS完成对无向图的预处理，就能通过调用SAME-COMPONENT查询两个顶点是否位于同一个连通分量。

注意：下图中的Edge processed，是指定的边处理顺序。

Figure 19.1

CONNECTED-COMPONENTS(G)
    for each vertex v ∈ G.V
        MAKE-SET(v)
    for each edge (u, v) ∈ G.E
        if FIND-SET(u) ≠ FIND-SET(v)
            UNION(u, v)

SAME-COMPONENT(u, v)
    if FIND-SET(u) == FIND-SET(v)
        return TRUE
    else return FALSE

过程CONNECTED-COMPONENTS开始时，将每个顶点 \(v\) 放在自己的集合中。然后对于执行的将要处理的边 \((u, v)\)，将包含 \(u\) 和 \(v\) 的集合进行合并。处理完所有的边后，两个顶点在相同的连通分量中且与之对应的集合元素在同一集合内。因此，CONNECTED-COMPONENTS以这种方式计算出的集合，使得SAME-COMPONENT操作能确定两个顶点是否在相同的连通分量中。

21.2 不相交集合的链表表示

下图(a)给出了一个实现不相交数据结构的简单方法：每个集合用一个链表来表示；每个集合对象 \(set\) 包含 \(head\) 属性和 \(tail\) 属性（下图深色区域），\(head\) 属性指向表的第一个对象，\(tail\) 属性指向元素的最后一个对象；链表中的每个对象都包含一个集合成员、一个指向链表中下一个对象的指针和一个指向集合对象 \(set\) 的指针。

Figure 19.2

用这种链表表示，MAKE-SET操作和FIND-SET操作是非常方便的，只需要 \(\Omicron(1)\) 的时间。执行MAKE-SET(x)操作，只需要创建一个只有 \(x\) 对象的新链表。执行FIND-SET(x)操作，只需要沿着 \(x\) 返回集合对象的指针找到集合对象 \(set\)，然后返回 \(head\) 指向对象的成员。例如，在上图(a)中，FIND-SET(g)的调用返回 \(f\)。

合并的一个简单实现

Figure 19.3

在 \(n\) 个对象上的 \(2n-1\) 个操作序列需要 \(\Theta(n^2)\) 总时间，或者每个操作平均时间为 \(\Theta(n)\)。

一种加权合并的启发式策略

采用一种简单的加权合并的启发式策略，我们将链表长度作为权值并维护链表长度，合并时将短的链表拼接到长的链表末尾。

定理：使用不相交集合的链表表示和加权合并的启发式策略，一个具有 \(m\) 个MAKE-SET、UNION和FIND-SET操作的序列（其中有 \(n\) 个是MAKE-SET操作）需要的时间为 \(\Omicron(m+n\log n)\)。

21.3 不相交集合森林

在不相交集合更快的实现中，我们使用树来表示集合，树中每个结点包含一个成员，每棵树代表一个集合。在一个不相交集合森林（disjoint-set forest）中，每个成员仅指向它的父结点。每棵树的根是集合的代表，并且是自己的父结点。

Figure 19.4

虽然使用这种表示的直接算法并不比使用链式表示的算法快，但通过引入两种启发式策略（“按秩合并”和“路径压缩”），我们能得到一个渐近最优的不相交集合数据结构。

MAKE-SET操作简单地创建一棵只有一个结点的树，FIND-SET操作通过沿着指向父结点的指针找到树的根。这一通向根结点的简单路径上所访问的结点构成了查找路径（find path）。UNION操作使得一棵树的根指向另外一棵树的根。

改进运行时间的启发式策略

  1. 按秩合并（union by rank）：类似于链表实现中使用的加权合并启发式策略。使具有较少结点的树的根指向具有较多结点的树的根。
  2. 路径压缩（path compression）：在FIND-SET操作中，可以使查找路径中的每个结点直接指向根。

Figure 19.5

实现不相交集合森林的伪代码

MAKE-SET(x)创建一个只有 \(x\) 的单元集合，此时 \(x.rank=0\)。

FIND-SET(x)过程是一个两趟方法(two-pass method)，这里提供递归版本，第一趟是沿着查找路径向上找到树的根，第二趟是从根结点开始沿着查找路径向下更新每个结点。该过程不会改变任一结点的秩。

UNION操作需要分两种情况讨论，若两棵树的根的秩不相同，则将具有较小秩的根点的父指针指向具有较大秩的根结点；若两棵树的根的秩相同，则任意选择两个根中的一个作为父结点，并将它的秩加一。

MAKE-SET(x)
    x.p = x
    x.rank = 0

UNION(x, y)
    LINK(FIND-SET(x), FIND-SET(y))

LINK(x, y)    // union by rank
    if x.rank > y.rank
        y.p = x
    else x.p = y
        if x.rank == y.rank
            y.rank = y.rank + 1

FIND-SET(x)    // 路径压缩
    if x ≠ x.p    // not the root
        x.p = FIND-SET(x.p)    // the root becomes the parent
    return x.p    // return the root