并查集进阶：路径压缩与按秩合并的优化

2501_93894370

455人浏览 · 2025-10-31 19:00:36

2501_93894370 · 2025-10-31 19:00:36 发布

并查集进阶：路径压缩与按秩合并的优化

并查集（Disjoint Set Union, DSU）是一种高效处理不相交集合合并与查询操作的数据结构，广泛应用于连通性问题（如图的连通分量、最小生成树算法）。基本实现中，查找（find）和合并（union）操作可能导致树结构退化，使时间复杂度恶化至$O(n)$。为优化性能，引入路径压缩和按秩合并两种技术，能将摊还时间复杂度降至$O(\alpha(n))$（其中$\alpha(n)$是反阿克曼函数，增长极慢，近乎常数级）。下面我将逐步解释这些优化原理、实现方法及代码示例。

1. 基本问题：为什么需要优化？

在基础并查集中，每个集合用一棵树表示，节点指向父节点（根节点指向自身）。
查找操作（find）需递归向上遍历到根节点。若树退化成链表（如频繁合并导致高度增加），查找时间复杂度为$O(n)$。
合并操作（union）若随意连接两棵树，可能加剧高度增长。
优化目标：通过路径压缩和按秩合并，控制树高度，使查找和合并操作高效。

2. 路径压缩（Path Compression）

原理：在查找操作中，将查询路径上的所有节点直接指向根节点，从而“压缩”路径。后续查找只需一步。
优点：减少树高度，摊还时间复杂度显著降低。
实现：递归查找时，更新父指针。公式化描述：
- 设$p[x]$表示节点$x$的父节点。
- 查找操作：$ \text{find}(x) = \begin{cases} x & \text{if } p[x] = x \ p[x] = \text{find}(p[x]) & \text{otherwise} \end{cases} $
代码示例（Python实现）：

def find(x, parent):
    if parent[x] != x:
        parent[x] = find(parent[x], parent)  # 递归压缩路径
    return parent[x]

3. 按秩合并（Union by Rank）

原理：在合并操作时，优先将秩（rank）较小的树合并到秩较大的树中。秩是树高度的上界（非精确高度），初始为0。
优点：防止树高度爆炸性增长，确保树相对平衡。
实现步骤：
1. 维护一个秩数组$\text{rank}$，初始化所有节点秩为0。
2. 合并两棵树时，比较根节点秩：
  - 若秩不同，将低秩树根指向高秩树根。
  - 若秩相同，任选一树作为根，并增加其秩（因高度可能增加）。
- 公式化描述：设$\text{root}_x$和$\text{root}_y$为两棵树根： $$ \text{union}(x,y) = \begin{cases} \text{root}_y \text{ 指向 } \text{root}_x & \text{if } \text{rank}[\text{root}_x] > \text{rank}[\text{root}_y] \ \text{root}_x \text{ 指向 } \text{root}_y & \text{if } \text{rank}[\text{root}_x] < \text{rank}[\text{root}_y] \ \text{root}_y \text{ 指向 } \text{root}_x \text{ 且 } \text{rank}[\text{root}_x] \gets \text{rank}[\text{root}_x] + 1 & \text{if } \text{rank}[\text{root}_x] = \text{rank}[\text{root}_y] \end{cases} $$
代码示例（Python实现）：

def union(x, y, parent, rank):
    root_x = find(x, parent)  # 使用路径压缩的find
    root_y = find(y, parent)
    if root_x == root_y:
        return  # 已在同一集合
    # 按秩合并
    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    elif rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        parent[root_y] = root_x
        rank[root_x] += 1  # 秩相同，增加秩

4. 完整优化实现与时间复杂度分析

结合使用：路径压缩和按秩合并互补。路径压缩减少单次查找开销，按秩合并控制长期高度增长。二者结合实现摊还$O(\alpha(n))$时间复杂度。
完整代码（Python类实现）：

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))  # 初始化父指针
        self.rank = [0] * size  # 初始化秩数组
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False  # 无需合并
        # 按秩合并
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True  # 合并成功

时间复杂度分析：
- 单次操作：最坏情况$O(\log n)$，但摊还分析证明平均为$O(\alpha(n))$。
- $\alpha(n)$是反阿克曼函数，满足$\alpha(n) \leq 4$对于所有实际$n$（如$n \leq 10^{600}$），因此近乎常数时间。
- 优化后，并查集在大型数据集（如百万节点）中依然高效。