CS61B 课程笔记（Lecture 20 Disjoint Sets)

不相交集合简介

不相交集合是一种数据结构，用于处理元素之间的连接性问题。它支持以下基本操作：

连接（connect）或并集（union） - 将两个元素合并到同一个集合中。
查询连接（isConnected） - 检查两个元素是否在同一个集合中。
查找根（find） - 查找某个元素的根节点。

关键观察

连接性是一个等价关系，表示两个对象在同一个集合中。
连接操作可以看作是将一个集合的所有元素移动到另一个集合中。

算法实现

1. 快速查找（Quick Find）

数组表示：使用一个长度为 \(N\) 的数组 id[]，其中 id[i] 表示元素 i 的桶编号。

连接操作：

void connect(int p, int q) {
    int pid = id[p];
    int qid = id[q];
    for (int i = 0; i < N; i++) {
        if (id[i] == pid) {
            id[i] = qid;
        }
    }
}

时间复杂度：\(O(N)\)（需要遍历整个数组）。

查询连接操作：

1
2
3

boolean isConnected(int p, int q) {
    return id[p] == id[q];
}

时间复杂度：\(O(1)\)。

总体时间复杂度：进行 \(M\) 次操作的总时间为 \(O(MN)\)。

2. 快速并查集（Quick Union）

数组表示：id[i] 表示元素 i 的父节点。

连接操作：

void connect(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    id[rootP] = rootQ;
}

int find(int p) {
    while (p != id[p]) {
        p = id[p];
    }
    return p;
}

时间复杂度：最坏情况下为 \(O(N)\)（需要查找根）。

查询连接操作：

1
2
3

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

时间复杂度：\(O(N)\)。

总体时间复杂度：进行 M 次操作的总时间为 \(O(NM)\)。

3. 加权快速并查集（Weighted Quick Union）

在连接时，总是将较小树的根连接到较大树的根。

连接操作：

void connect(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP != rootQ) {
        if (size[rootP] < size[rootQ]) {
            id[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            id[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
    }
}

时间复杂度：最坏情况下为 \(O(\log N)\)。

4. 加权快速并查集与路径压缩（Weighted Quick Union with Path Compression）

在查找时，将沿途的所有节点直接连接到根。

查找操作：

int find(int p) {
    if (p != id[p]) {
        id[p] = find(id[p]); // 路径压缩
    }
    return id[p];
}

连接和查询操作同上，但由于路径压缩的优化，操作复杂度更低。
总体时间复杂度：进行 \(M\) 次操作的总时间为 \(O(M \log^* N)\)，其中 \(\log^* N\) 是极其缓慢增长的函数，对于实际应用而言通常在 5 以内。