张芷铭的个人博客

#数据结构 #并查集 #Union-Find #算法

并查集（Union-Find）是处理动态连通性问题的高效数据结构，通过路径压缩和按秩合并，Find 和 Union 操作可达近乎 O(1) 时间复杂度。

核心概念

并查集管理若干不相交集合，支持两个核心操作：

  • Find：查找元素所属集合的代表元
  • Union：合并两个不相交集合

底层采用森林表示法：每棵树代表一个集合，根节点为集合代表元。初始时每个元素自成一树，父节点指向自身。

数学性质

集合满足等价关系三性质：

  • 自反性：元素与自身连通（MakeSet 保证）
  • 对称性：若 x 与 y 连通，则 y 与 x 连通
  • 传递性：若 x 与 y 连通，y 与 z 连通，则 x 与 z 连通

优化策略

未优化的并查集在树退化为链时，Find 和 Union 时间复杂度为 O(n)。通过两种优化可降至 O(α(n))。

路径压缩

Find 时将查询路径上所有节点直接指向根节点，扁平化树结构。后续查询可一步定位根节点。

按秩合并 / 按大小合并

合并时将较小树挂到较大树下，避免树退化为链：

  • 按大小：维护 size[] 记录集合节点数
  • 按秩：维护 rank[] 记录树高度上限

两种优化组合后，均摊时间复杂度为 O(α(n))，α(n) 为阿克曼函数反函数，实际可视为常数。

代码实现

基础版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class UnionFindBasic:
    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

路径压缩 + 按秩合并（推荐）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class UnionFindOptimized:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        # 路径压缩
        while self.parent[x] != root:
            next_parent = self.parent[x]
            self.parent[x] = root
            x = next_parent
        return root

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

经典应用

应用场景说明
Kruskal 最小生成树判断边端点是否连通，避免形成环
网络连通性检测动态判断节点连通性
图像连通区域标记将相邻像素划分为同一区域
岛屿数量问题动态添加陆地，实时查询岛屿数

扩展：带权并查集

基础并查集仅处理连通性，带权并查集通过 weight[] 数组记录节点与父节点的关系权重，可处理关系传递问题。

经典应用：食物链问题，weight[x] 表示 x 相对于父节点的关系（0=同类，1=吃父节点，2=被父节点吃），通过模 3 运算保证关系周期性。

实现注意事项

  • 非递归 Find 避免大规模数据栈溢出
  • 元素非连续整数时用哈希表映射
  • 动态扩容可用哈希表替代数组

Comments