不相交集合数据结构

概述

不相交集合数据结构（Disjoint-Set / Union-Find / 并查集）维护一组不相交动态集合 $S=\{S_1,S_2,\dots ,S_k\}$ 的划分，支持高效的合并（UNION）和查询（FIND-SET）操作。它是处理等价关系和连通分量问题的核心数据结构。

定义

不相交集合数据结构

维护一个元素集合 $S$ 的一个划分（partition），即一组两两不相交的子集 $\{S_1,S_2,\dots ,S_k\}$，满足：

• ${\bigcup }_{i=1}^k{S}_i=S$
• 对所有 $i\ne j$，$S_i\cap S_j=\varnothing$

每个子集 $S_i$ 称为一个集合（set），每个集合有一个代表（representative）来标识该集合。

三个核心操作

操作	语法	功能
MAKE-SET	MAKE-SET(x)	创建一个仅含元素 $x$ 的新单元素集合
UNION	UNION(x, y)	将包含 $x$ 的集合与包含 $y$ 的集合合并
FIND-SET	FIND-SET(x)	返回包含 $x$ 的集合的代表元素

操作的不变式

• FIND-SET(x) = FIND-SET(y) 当且仅当 $x$ 和 $y$ 属于同一个集合
• MAKE-SET(x) 之后，$x$ 单独构成一个集合，FIND-SET(x) = x

典型应用

1. 连通分量维护：在无向图中，动态添加边时维护连通分量
2. 等价关系维护：判断两个元素是否属于同一等价类
3. 最小生成树（Kruskal 算法）：判断加入边是否会形成环
4. 迷宫生成：随机化 Prim/Kruskal 迷宫生成算法

发明历史

• 1973：Hopcroft & Ullman 提出按秩合并，达到 $O(m\lg n)$
• 1975：Tarjan 提出路径压缩，与按秩合并结合达到 $O(m\alpha (n))$
• 1989：Fredman & Saks 证明 $\Omega (\alpha (n))$ 的下界，确认 $\alpha (n)$ 是最优的

四种实现的复杂度对比

实现方式	MAKE-SET	FIND-SET	UNION	$m$ 次操作总复杂度
链表（无优化）	$O(1)$	$O(1)$	$O(n)$	$O(mn)$
链表 + 加权合并启发式	$O(1)$	$O(1)$	$O(1)$*	$O(m+n\lg n)$
森林 + 按秩合并	$O(1)$	$O(\lg n)$	$O(1)$*	$O(m\lg n)$
森林 + 按秩合并 + 路径压缩	$O(1)$	$O(\alpha (n))$	$O(\alpha (n))$	$O(m\alpha (n))$

*UNION 通过两次 FIND-SET + 一次 LINK 实现，均摊意义下的代价。

关键观察

最优实现（森林 + 按秩合并 + 路径压缩）的每次操作均摊代价为 $O(\alpha (n))$，其中 $\alpha (n)$ 是反阿克曼函数。由于 $\alpha (n)\le 4$ 对所有实际可能的 $n$ 成立，因此在实践中可以视为 $O(1)$。

第21章：最小生成树

Kruskal算法是并查集最经典的应用场景。算法将图的边按权排序后逐条处理：对每条边 (u,v)，使用 FIND-SET(u) ≠ FIND-SET(v) 判断 u 和 v 是否已在同一连通分量中。若不在同一分量，则 UNION(u,v) 合并两个分量并将边加入MST。使用按秩合并+路径压缩的并查集，Kruskal总时间 O(E α(V))，其中 α 是反阿克曼函数。

参见

• 加权合并启发式 — 链表表示中的优化策略
• 不相交集合森林 — 基于有根树的高效表示
• 按秩合并 — 森林表示中的合并优化
• 路径压缩 — FIND-SET 的路径优化
• 反阿克曼函数 — 复杂度分析中的关键函数
• 聚合分析 — 加权合并启发式的分析方法
• 势能方法 — 路径压缩+按秩合并的分析方法