slide:cs61b 2020 lec14 ds1 disjoint sets - Google 幻灯片

Reading:9.1 Introduction · Hug61B (gitbooks.io)

code:Case Study: Union-Find (princeton.edu)

Disjoint Sets简介

如果两个集合没有共同元素，则称它们为不相交集合。一个不相交集合（或者称为并查集）数据结构用于追踪固定数量的元素，这些元素被划分为多个不相交集合。该数据结构具有两个操作：

connect(x, y): 连接 x 和 y。也称为 union。
isConnected(x, y): 如果 x 和 y 连接（即属于同一集合），则返回true。

不相交集合数据结构有一定数量的元素，每个元素最初都位于自己的子集中。通过对某些元素 x 和 y 调用 connect(x, y)，我们可以将子集合并在一起。

例如，假设我们有四个元素，我们将它们称为 A、B、C、D。初始时，每个元素都在自己的集合中：

调用 connect(A, B) 后：

请注意，子集 A 和 B 被合并。让我们来检查一些 isConnected 调用的输出：

1 2	CodeisConnected(A, B) -> true isConnected(A, C) -> false

调用 connect(A, D) 后：

我们找到了 A 所属的集合，并将其与 D 所属的集合合并，形成了一个大的 A、B、D 集合。C 保持不变。 isConnected(A, D) -> true isConnected(A, C) -> false

有了这个直观理解，让我们正式定义一下我们的不相交集合接口是什么样子的。作为提醒，一个接口确定了一个数据结构应该具有的行为（但不包括实现方法）。现在，我们只处理非负整数集合。这并不是一个限制，因为在实际应用中，我们可以为我们想要表示的任何内容分配整数值。

public interface DisjointSets {
    /** 连接两个项目 P 和 Q */
    void connect(int p, int q);

    /** 检查两个项目是否连接 */
    boolean isConnected(int p, int q); 
}

除了学习如何实现一个迷人的数据结构之外，这一章还将是一个了解数据结构实现如何演变的机会。我们将讨论四个不相交集合设计的迭代过程：Quick Find → Quick Union → Weighted Quick Union (WQU) → WQU with Path Compression。我们将看到设计决策如何极大地影响渐近运行时间和代码复杂度。

快速查找Quick Find

现在我们来解决如何实现我们的 DisjointSets 接口所需的行为。我们的挑战是跟踪集合成员关系。

集合列表

直观地，我们可能首先考虑将不相交集合表示为一个集合列表，例如 List<Set<Integer>>。

例如，如果我们有 N=6 个元素，并且还没有连接任何元素，我们的集合列表看起来像：[{0}, {1}, {2}, {3}, {4}, {5}, {6}]。看起来不错。然而，考虑如何完成像 connect(5, 6) 这样的操作。我们将不得不遍历多达 N 个集合来找到5，以及多达 N 个集合来找到6。我们的运行时间变为 O(N)。而且，如果你试图实现这个，代码会非常复杂。

要记住的教训是 初始设计决策决定了我们的代码复杂度和运行时间。

快速查找

让我们考虑另一种方法，使用一个 整数数组。

数组的索引表示我们集合的元素。
索引处的值是它所属的集合编号。

例如，我们将 {0, 1, 2, 4}, {3, 5}, {6} 表示为：

数组索引（0…6）是元素。id[i] 处的值是它所属的集合。具体的集合编号并不重要，只要同一集合中的所有元素共享相同的id。

`connect(x, y)`

让我们看看连接操作如何工作。当前，id[2] = 4 和 id[3] = 5。调用 connect(2, 3) 后，所有id为4和5的元素应该具有相同的id。现在暂时将它们全部赋值为5：

`isConnected(x, y)`

要检查 isConnected(x, y)，我们只需检查 id[x] == id[y]。请注意，这是一个常数时间操作！

我们将此实现称为 “快速查找”，因为查找元素是否相连需要常数时间。

总结和代码

实现方式	构造函数	`connect`	`isConnected`
集合列表	Θ(N)	O(N)	O(N)
快速查找	Θ(N)	Θ(N)	Θ(1)

N = 不相交集合数据结构中的元素数量

public class QuickFindDS implements DisjointSets {

    private int[] id;

    /* Θ(N) */
    public QuickFindDS(int N){
        id = new int[N];
        for (int i = 0; i < N; i++){
            id[i] = i;
        }
    }

    /* 需要遍历数组 => Θ(N) */
    public void connect(int p, int q){
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++){
            if (id[i] == pid){
                id[i] = qid;
            }
        }
    }

    /* Θ(1) */
    public boolean isConnected(int p, int q){
        return (id[p] == id[q]);
    }
}

快速合并Quick Union

假设我们优先考虑使 connect 操作快速。我们仍然将使用数组来表示我们的集合。但是，与其使用一个id，我们将每个项目分配给其父项的索引。如果一个项目没有父项，那么它就是一个 ‘根’，我们为其分配一个负值。

这种方法使我们可以将我们的每个集合想象成一棵树。例如，我们将 {0, 1, 2, 4}, {3, 5}, {6} 表示为：

请注意，我们使用只有一个数组来表示集合。我们自己将其视为树。

对于快速合并，我们定义一个辅助函数 find(int item)，它返回项目所在树的根。例如，对于上面的集合，find(4) == 0，find(1) == 0，find(5) == 3 等。每个元素都有一个唯一的根。

`connect(x, y)`

要连接两个项目，我们找到每个项目所属的集合（它们各自树的根），并将其中一个作为另一个的子项。例如：

connect(5, 2)：

find(5) -> 3
find(2) -> 0
设置 find(5) 的值为 find(2)，也就是 parent[3] = 0

请注意，元素3现在指向元素0，将两棵树/集合合并为一棵树。

在最佳情况下，如果 x 和 y 都是它们树的根，那么 connect(x, y) 就会简单地使 x 指向 y，这是一个 Θ(1) 的操作！（因此称为快速合并）

`isConnected(x, y)`

如果两个元素属于同一个集合，那么它们将在同一棵树中。因此，它们将具有相同的根。因此对于 isConnected(x, y)，我们只需检查 find(x) == find(y)。

性能

快速合并存在潜在的性能问题：树可能变得非常长。在这种情况下，找到一个项目的根 (find(item)) 就变得非常昂贵。考虑下面的树：

9.3.3

在最坏的情况下，我们必须遍历所有项目才能到达根，这是一个 Θ(N) 的运行时间。由于我们必须对 connect 和 isConnected 都调用 find，所以它们的运行时间都由 O(N) 上限约束。

总结和代码

实现方式	构造函数	`connect`	`isConnected`
集合列表	Θ(N)	O(N)	O(N)
快速合并	Θ(N)	O(N)	O(N)
快速查找	Θ(N)	Θ(N)	Θ(1)

N = 不相交集合数据结构中的元素数量

从运行时间表中，快速合并似乎比快速查找更差！但请注意，O(N) 是一个上限。当我们的树是平衡的时候，connect 和 isConnected 都表现得相当好。在下一节中，我们将看到如何保证它们的性能良好。

public class QuickUnionDS implements DisjointSets {
    private int[] parent;
    public QuickUnionDS(int num) {
        parent = new int[num];
        for (int i = 0; i < num; i++) {
            parent[i] = i;
        }
    }

    private int find(int p) {
        while (parent[p] >= 0) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public void connect(int p, int q) {
        int i = find(p);
        int j= find(q);
        parent[i] = j;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}