并查集（Union-Find）数据结构原理与应用

并查集是一种用于处理不相交集合合并及查询问题的树型数据结构。它支持两种基本操作：查找元素所属集合（Find）和合并两个集合（Union）。在解决动态连通性问题、图论中的连通分量计算等问题时非常高效。

一、基本概念与表示方法

并查集的核心思想是用一个数组（或字典）来表示元素的集合关系。每个元素对应数组中的一个位置，存储的值表示该元素的"父节点"。如果元素是根节点（集合代表），则存储一个特殊标记（通常是自己或负值）。

初始状态时，每个元素自成一个集合：

元素：0 1 2 3 4
父节点：0 1 2 3 4

二、基本操作实现

1. Find操作（查找根节点）

   • 从当前元素开始，沿着父节点指针向上遍历，直到找到根节点
   • 根节点的特征是：父节点指向自己

   def find(x, parent):
       while parent[x] != x:  # 不是根节点
           x = parent[x]     # 向上移动
       return x
   

2. Union操作（合并集合）

   • 找到两个元素各自的根节点
   • 如果根节点不同，将其中一个根节点的父节点指向另一个根节点

   def union(x, y, parent):
       root_x = find(x, parent)
       root_y = find(y, parent)
       if root_x != root_y:  # 不在同一集合
           parent[root_x] = root_y  # 合并
   

三、优化策略

基础实现可能产生退化的链状结构，导致操作效率降低。需要以下优化：

1. 按秩合并（Union by Rank）

   • 记录每个树的深度（秩），总是将较浅的树合并到较深的树下
   • 避免树过高，保持相对平衡

   def union(x, y, parent, rank):
       root_x = find(x, parent)
       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
   

2. 路径压缩（Path Compression）

   • 在Find操作过程中，将路径上的所有节点直接连接到根节点
   • 扁平化树结构，加速后续查询

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

四、完整实现示例

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    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(α(n))
• α(n)是反阿克曼函数，增长极其缓慢
• 对于实际应用规模，可视为常数时间操作

六、典型应用场景

1. 动态连通性问题：判断网络中两个节点是否连通
2. 最小生成树算法：Kruskal算法中的集合管理
3. 图像处理：连通区域标记
4. 社交网络：好友关系中的连通分量计算
5. 编译器优化：变量等价类分析

并查集通过简单的数组结构和巧妙的优化策略，高效解决了动态集合合并与查询问题，是算法设计中"以空间换时间"的经典范例。