跳转到内容
← 返回算法
数据结构计算机科学 · 数据结构约 25 分钟阅读

并查集

Union-Find (Disjoint Set Union)

一张有十亿用户的社交网络，好友关系不断新增。系统要随时回答："张三和李四，通过朋友的朋友的朋友……能不能连上？" 每来一对询问就跑一次深度优先搜索？一次搜索要遍历整张图（$O(n + m)$）；十亿节点上做几百万次询问，等于把整张网络扫几百万遍——根本跑不动。

并查集不相交集合路径压缩最小生成树

一张有十亿用户的社交网络，好友关系不断新增。系统要随时回答："张三和李四，通过朋友的朋友的朋友……能不能连上？"

每来一对询问就跑一次深度优先搜索？一次搜索要遍历整张图（$O(n + m)$）；十亿节点上做几百万次询问，等于把整张网络扫几百万遍——根本跑不动。

并查集（Union-Find，又称 Disjoint Set Union，DSU）把每次"合并两个人"和"查询是否连通"的代价压到摊销几乎 $O(1)$：哪怕节点数是十亿，每次操作平均只需常数级别的几步。它的实现简单得令人意外——核心就是一个 parent 数组——但背后的分析涉及计算机科学史上最精妙的摊销分析之一（见下文 Tarjan 1975 的结果）。

核心接口

并查集支持三种操作：

  • make_set(x)：将 $x$ 初始化为一个单元素集合
  • find(x)：返回 $x$ 所在集合的代表（Representative），同一集合内所有元素返回相同代表
  • union(x, y)：合并 $x$ 和 $y$ 所在的两个集合

利用这三个操作，判断 $a, b$ 是否连通只需：find(a) == find(b)。

数组实现：从朴素到高效

朴素方案：Quick-Find

用数组 id[]，id[i] 存储节点 $i$ 的集合 ID。

  • find(x)：返回 id[x]，$O(1)$
  • union(x, y)：将 y 集合的所有节点的 id 改为 x 集合的 id，$O(n)$

查询快到极致，合并慢到不能用：$m$ 次合并要 $O(nm)$。n=106n = 10^6、m=106m = 10^6 时是 101210^{12} 次数组写入，几十分钟起步。

朴素方案：Quick-Union

用数组 parent[]，每个节点指向"父节点"，根节点指向自己，根节点是集合代表。find(x) 沿 parent 指针向上直到根，代价是树高，最坏 $O(n)$；union(x, y) 找到两者根节点，把一个根指向另一个根，找到根之后只需 $O(1)$。

树可能退化成链表，这不是理论上的担忧而是最平常的输入就能触发。看这段循环：

python
for i in range(n - 1):
    union(i, i + 1)          # 总把 root(i) 挂到 root(i+1) 之下
```

$n = 8$ 时得到的 parent 数组是 [1,2,3,4,5,6,7,7]——一条 0→1→⋯→70 \to 1 \to \cdots \to 7 的链，find(0) 要走 7 步。把 $n$ 换成 10610^6，find(0) 就是一百万次指针跳转。而"把相邻编号连起来"是图算法里最不起眼的一种输入。

优化一：按秩合并（Union by Rank）

合并时不再随意挑，而是让矮树挂到高树下面，用 rank[root] 记录树高的一个上界。归纳可证：秩为 $r$ 的树至少含 2r2^r 个节点，所以 r≤log⁡2nr \le \log_2 n，树高被压到 O(log⁡n)O(\log n)，find 也就变成 O(log⁡n)O(\log n)——而且是最坏情况的 O(log⁡n)O(\log n)，不是摊还的。

优化二：路径压缩（Path Compression）

在 find 操作中，访问路径上的每个节点时，直接把它的父节点设为根：

python
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 路径压缩（递归版）
    return parent[x]
```

这不改变集合的逻辑结构，只是把树"压扁"，使后续查询更快。注意一个反直觉之处：find 是个查询操作，但它会改写数据结构。这就是为什么并查集的分析必须是摊还分析——单次 find 可能很贵，但它顺手把路径变短了，账要记在后面所有查询的头上。

走一遍：8 个元素的合并与压缩

只看伪代码很难对"压缩"有感觉。把 8 个元素 $0..7$ 走完整套（按秩合并 + 路径压缩），每一步给出 parent 数组快照。初始 parent = [0,1,2,3,4,5,6,7]，全部 rank = 0。

步操作两根的秩决定parent 数组秩变化
1union(0,1)0, 0秩相等，任选一个当根：1 挂到 0[0,0,2,3,4,5,6,7]rank[0]=1
2union(2,3)0, 03 挂到 2[0,0,2,2,4,5,6,7]rank[2]=1
3union(0,2)1, 12 挂到 0[0,0,0,2,4,5,6,7]rank[0]=2
4union(4,5)0, 05 挂到 4[0,0,0,2,4,4,6,7]rank[4]=1
5union(6,7)0, 07 挂到 6[0,0,0,2,4,4,6,6]rank[6]=1
6union(4,6)1, 16 挂到 4[0,0,0,2,4,4,4,6]rank[4]=2
7union(0,4)2, 24 挂到 0[0,0,0,2,0,4,4,6]rank[0]=3

七次合并之后，森林长成这样（括号里是秩）：

text
                0 (3)
           /    |    \
          1     2     4 (2)
                |    /  \
                3   5    6 (1)
                         |
                         7
```

节点 7 在深度 3 上。现在调用 find(7)：

阶段走过的路径指针跳转次数之后的 parent
压缩前7→6→4→07 \to 6 \to 4 \to 03[0,0,0,2,0,4,4,6]
压缩后parent[7]=0、parent[6]=0（parent[4] 本已是 0）下次都是 1[0,0,0,2,0,4,0,0]

再来一次 find(3)：路径 3→2→03 \to 2 \to 0，2 次跳转，压缩后 parent[3]=0，数组变成 [0,0,0,0,0,4,0,0]。此时只剩节点 5 还在深度 2（5→4→05 \to 4 \to 0）——两次查询就把这棵高度 3 的树基本拍平了，而且没有任何额外的重建步骤，压缩完全是查询路径上的副产品。

这里藏着一个值得注意的细节：rank[0] 仍然是 3，而树的实际高度已经降到 2。秩只是高度的上界，路径压缩从不下调它。 这不是 bug——如果压缩后要重算秩，就得知道整棵子树的形状，代价立刻回到 $O(n)$。用一个稍微偏大的上界换 $O(1)$ 的维护，是这套设计里第二个"故意不精确"的地方（第一个是 find 顺手改写结构）。

两个优化组合：近乎 $O(1)$

两个优化不是可选项的自由组合，四种搭配的复杂度差得很远：

配置单次 find$m$ 次操作总代价
都不用（朴素 quick-union）$O(n)$ 最坏$O(mn)$
只按秩合并O(log⁡n)O(\log n) 最坏O(mlog⁡n)O(m\log n)
只路径压缩O(log⁡n)O(\log n) 摊还Θ(n+mlog⁡1+m/nn)\Theta(n + m\log_{1+m/n} n)；m=Θ(n)m = \Theta(n) 时即 Θ(nlog⁡n)\Theta(n\log n)
两者都用O(α(n))O(\alpha(n)) 摊还Θ(m α(n))\Theta(m\,\alpha(n))

这张表最该注意的是中间两行：它们的渐近界看起来一样，性质完全不同。 按秩合并给的是最坏保证——每一次 find 都不超过 log⁡n\log n；路径压缩给的是摊还保证——单次可能走满 $n$ 步，只是这种昂贵操作不会连续出现。对延迟敏感的在线系统，这两者不能互换。第三行那个奇怪的 log⁡1+m/nn\log_{1+m/n} n 来自 Tarjan 与 van Leeuwen 1984 年对各种链接策略的系统分析：查询越密（$m/n$ 越大），单次摊还代价越低，因为压缩的收益被更多查询分摊了。

两者都用时，任意 $m$ 次操作的总时间是 O(m⋅α(n))O(m \cdot \alpha(n))，其中 α(n)\alpha(n) 是 Ackermann 函数的反函数。这一结果由 Robert Tarjan（图灵奖得主）在 1975 年证明，是算法理论中摊销分析的里程碑。

$\alpha(n)$ 到底有多小

"α(n)≤4\alpha(n) \le 4" 这句话经常被含糊地说成"实践中是常数"，但它可以给出精确的门槛。按 CLRS 的定义，递归地设 A0(j)=j+1A_0(j) = j+1、Ak(j)=Ak−1(j+1)(j)A_k(j) = A_{k-1}^{(j+1)}(j)（上标表示函数迭代 $j+1$ 次），则 α(n)=min⁡{k:Ak(1)≥n}\alpha(n) = \min\{k : A_k(1) \ge n\}。把前几层算出来：

  • A1(j)=2j+1A_1(j) = 2j + 1，所以 A1(1)=3A_1(1) = 3
  • A2(j)=2j+1(j+1)−1A_2(j) = 2^{j+1}(j+1) - 1，所以 A2(1)=7A_2(1) = 7
  • A3(1)=A2(A2(1))=A2(7)=28×8−1=2047A_3(1) = A_2(A_2(1)) = A_2(7) = 2^8 \times 8 - 1 = 2047
  • A4(1)=A3(A3(1))=A3(2047)≥22048A_4(1) = A_3(A_3(1)) = A_3(2047) \ge 2^{2048}

于是有一张完全具体的表：

$n$ 的范围α(n)\alpha(n)
n≤2n \le 20
$n = 3$1
4≤n≤74 \le n \le 72
8≤n≤20478 \le n \le 20473
2048≤n≤A4(1)2048 \le n \le A_4(1)4

22048≈106162^{2048} \approx 10^{616}。可观测宇宙里的原子数约 108010^{80}。就算给每个原子分配一个并查集元素，$n$ 也才 108010^{80}，离 1061610^{616} 还差 536 个数量级——α(n)\alpha(n) 停在 4，永远不会到 5。 这就是"渐近上非常数、工程上完全是常数"的确切含义。

为什么 $\alpha(n)$ 不是真正的 $O(1)$？

上面那张表看下来，很容易得出"那不如就当它是常数"的结论。工程上确实可以，但理论上它确实不是 $O(1)$，而且这不是分析不够紧的问题。1979 年 Tarjan 证明：在一类"可分指针机"（separable pointer machine）模型下，任何在线维护不相交集合的算法都需要 Ω(m α(m,n))\Omega(m\,\alpha(m,n)) 时间——路径压缩式的算法族里不存在线性解法。1989 年 Fredman 和 Saks 在更强的 cell-probe 模型下给出了 Ω(α(n))\Omega(\alpha(n)) 的摊还下界。

所以 Θ(m⋅α(n))\Theta(m \cdot \alpha(n)) 既是上界也是下界。并查集是少数几个我们确切知道最优代价、且这个代价恰好不是线性的基础问题——这在算法理论里相当罕见，通常我们要么证不出下界，要么下界与上界还隔着一道缝。

经典应用

Kruskal 最小生成树

Kruskal 算法（Kruskal 1956）按边权从小到大排序，逐条加边，若边两端不连通（用 find 判断）则加入生成树（用 union 合并）。并查集是 Kruskal 高效实现的核心。

值得算一下代价的分布：排序 $E$ 条边是 O(Elog⁡E)O(E\log E)，并查集部分是 O(E α(V))O(E\,\alpha(V))。以 V=106V = 10^6、E=5×106E = 5\times10^6 为例，log⁡2E≈22\log_2 E \approx 22，排序约 1.1×1081.1\times10^8 次比较，并查集约 5×106×4=2×1075\times10^6 \times 4 = 2\times10^7 步——并查集只占总代价的百分之几。所以 Kruskal 的实现优化第一站永远是排序（比如边权是小整数时换基数排序），而不是并查集。这也解释了为什么"并查集近乎 $O(1)$"这件事在实践中很少被注意到：它太便宜，从来不是瓶颈。

检测无向图中的环

逐边加入，每次检查 find(u) == find(v)——若相等说明成环，否则 union(u, v)。这也是 Kruskal 的正确性依据：贪心地取最小边，只要不成环就一定属于某棵最小生成树。

网络连通性维护

网络节点逐步相连时（如社交网络、通信网），实时回答"$a$ 和 $b$ 能通信吗？"注意这里的关键限定是只增不减——边只会加入，不会消失。一旦允许删边，并查集就完全失效（见下文"局限"）。

图像处理：连通区域标记

二值图像的连通域标记（Connected Components Labeling）是并查集最古老的工业应用之一，Rosenfeld 与 Pfaltz 在 1966 年的论文里就给出了经典的两遍扫描法：第一遍逐行扫描像素，给每个前景像素一个临时标签，遇到"左边和上边的标签不同但同属一个连通块"时不立刻改写，而是往等价表里记一次 union；第二遍再用 find 把所有临时标签换成代表标签。

这个设计的精髓在于第一遍不需要回头。如果不用并查集，发现两个标签等价时就得回去把整片已扫过的像素重新编号；有了并查集，等价关系可以先攒着，最后一次结算。对一张 4000×30004000\times3000 的图（1.2×1071.2\times10^7 个像素），这是"扫两遍"和"最坏扫上千遍"的区别。

离线 LCA（最近公共祖先）

Tarjan 离线 LCA 算法用并查集以线性时间批量回答所有 LCA 查询。它的思路是对树做一次 DFS：回溯离开子树 $v$ 时，把 $v$ 所在集合并入它父亲的集合。这样在处理节点 $u$ 时，任何已经访问完的节点 $w$ 所在集合的代表，恰好就是 LCA(u,w)\mathrm{LCA}(u, w)——并查集在这里维护的不是"连通性"，而是"当前已经归拢到哪个祖先名下"。

这是并查集一类值得注意的用法：它的语义可以被重新解释。同一套 parent 数组，在 Kruskal 里代表"同一个连通块"，在 Tarjan LCA 里代表"同一个祖先名下"，在类型推导里代表"同一个类型"。并查集本质上维护的是一个等价关系，而不是任何具体的图结构。

现场：编译器里的并查集

并查集最不像"图算法"的一个应用在编译器的类型推导里。Hindley-Milner 类型推导的核心操作叫合一（unification）：把两个可能含未知类型变量的类型强行变得相等，过程中不断发现"这个类型变量其实就是那个类型变量"。

这正是并查集的形状：每个类型变量是一个元素，union 表示"这两个变量指同一个类型"，find 返回这一等价类的代表（如果这一类已经确定了具体类型，代表节点上就挂着那个类型）。

Rust 编译器把自己的这套实现单独抽出来发布成了 crate ena（名字取自希腊语的"一"），核心类型是 UnificationTable。它按 Tarjan 的经典方案实现：union 时把一个键变成指向另一个键的"重定向"，根节点上带值和秩。rustc 里创建一个新的类型变量（fresh_ty_var）就是在并查集里开一个新的单元素集合。

真正有意思的是它多出的那个能力：快照与回滚。ena 允许在任意时刻给整张表打快照，之后的修改可以提交，也可以整体撤销。编译器需要这个，是因为类型检查经常要试探——先假设这里插入一次自动解引用（coercion）能让类型对上，试完不行就退回原状。

这个需求和路径压缩是天然冲突的：压缩会改写一堆和本次 union 无关的 parent 指针，回滚时这些改写也必须一并撤销。所以可回滚的并查集要么维护一份完整的 undo 日志（ena 的做法），要么干脆放弃路径压缩、只用按秩合并——后者正是可持久化并查集的处理方式，代价是复杂度从 O(α(n))O(\alpha(n)) 退回 O(log⁡n)O(\log n)。

一个反向的注脚：合一问题并不非要并查集。Paterson 与 Wegman 在 1978 年给出了真正线性时间的合一算法，做法是用无界的指针列表表示等价关系，刻意绕开并查集那个 α(n)\alpha(n) 因子。但主流编译器几乎都没采用——因为 α(n)≤4\alpha(n) \le 4，那个理论上的改进买不到任何可测量的收益，却要付出实现复杂度和"不支持回滚"的代价。 这是本文最该记住的工程判断：当一个因子已经小到 4，继续优化它的收益是零，而为它牺牲的可回滚性、可读性都是实打实的损失。

加权并查集：带权信息的扩展

并查集可以扩展为加权并查集（Weighted DSU），在 parent 指针上记录从子节点到父节点的权重（如相对距离、差值），路径压缩时把沿路的权重累加起来同步更新。典型用途是判断两点之间是否存在特定的量化关系（如大小关系、模余关系），广泛用于算法竞赛的约束系统问题。

这里的要求是权重必须构成一个群：能复合（路径上的权重相加）、有逆元（反向走时取负）。这一点和线段树的懒惰标记必须"可结合复合"是同一类约束——能挂到数据结构上的附加信息，取决于它有没有足够好的代数性质。

可持久化并查集

标准并查集不支持"回滚"（撤销 union 操作）。可持久化并查集（Persistent DSU） 用可持久化数组（基于主席树）实现，可以在 O(log⁡n)O(\log n) 内查询"历史上任意时刻的集合状态"。代价是路径压缩会破坏持久化，所以只能用按秩合并，时间从 O(α(n))O(\alpha(n)) 退回 O(log⁡n)O(\log n)——这与上一节 ena 面对的是同一个矛盾，只是 ena 选了"保留压缩 + 记 undo 日志"，可持久化并查集选了"放弃压缩"。

并查集的局限

并查集支持合并（union），但不支持分裂（split）——一旦合并，无法把集合再拆开，也就不支持删除。原因在结构本身：parent 数组只记录"谁挂在谁下面"，不记录这条边是哪一次 union 造成的。删掉图里的一条边 $(u,v)$ 之后，$u$ 和 $v$ 可能仍然通过其他路径相连，也可能不再相连——而并查集里没有任何信息能区分这两种情形。它压缩掉的恰恰是"连通性是怎么来的"这个信息，而这正是删边时唯一有用的信息。这和跳表、哈希表的取舍是同一个道理：每一种压缩都在丢弃某类未来的提问能力。

允许删边的问题叫全动态连通性（fully dynamic connectivity），需要完全不同的机器。Holm、de Lichtenberg 与 Thorup 在 2001 年的《ACM 汇刊》论文给出了第一个确定性的多对数解法：每次插入或删除边摊还 O(log⁡2n)O(\log^2 n)，连通性查询 O(log⁡n/log⁡log⁡n)O(\log n / \log\log n)。对比只增不减情形的 O(α(n))≤4O(\alpha(n)) \le 4，允许删除让代价从"常数"跳到了 log⁡2n\log^2 n——n=106n = 10^6 时约 400 步，整整两个数量级。这个差距就是"单调"这个假设的价值。

另一条路是 Link-Cut Tree（Sleator 与 Tarjan 1983），它维护的是森林而非任意图，支持 O(log⁡n)O(\log n) 摊还的连边与断边，是竞赛与部分离线算法里更常用的工具。

跨域连接

  • 最小生成树：按边权递增逐条加边、不成环就并入，这套贪心的可行性完全靠它撑着。但代价分布值得一看：排序占了绝大部分，并查集只占几个百分点——所以优化的第一站永远是排序。近乎常数的代价意味着它从来不是瓶颈，也因此很少被注意到。
  • 群：加权版本在指针上挂一个到父节点的相对量，路径压缩时沿途累加。这要求权重能复合、且有逆元，也就是构成一个群——反向走时取负，压缩才不会改变语义。能挂到数据结构上的附加信息，取决于它有没有足够好的代数性质。
  • 类型系统：类型推导里的合一就是它的另一副面孔：每个类型变量是一个元素，合并表示"这两个变量指同一类型"。编译器还额外需要回滚，因为类型检查常要试探；而路径压缩会改写大量与本次合并无关的指针，两者天然冲突，只能靠撤销日志或干脆放弃压缩来调和。
  • 相变：渗流实验里逐条随机加边、观察最大连通块何时贯穿整个系统，用的正是这个结构。它与"只增不减"这个设定完全契合：加边是单调的，而贯穿发生在一个尖锐的临界占据率附近——同一套单调性既是算法成立的前提，也是相变现象的前提。
  • 社会网络分析：连通分量回答的正是"能否通过熟人链联系上"。但真实关系会消失，而一旦允许删边，代价就从近乎常数跳到对数的平方——因为结构压缩掉的恰恰是"连通性是怎么来的"，而那正是删边时唯一有用的信息。单调这个假设的价值，可以被量化成这两个量级之差。

参考文献

  • Tarjan, R. E. "Efficiency of a Good But Not Linear Set Union Algorithm." Journal of the ACM 22(2), 215–225 (1975).
  • Tarjan, R. E. "A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets." Journal of Computer and System Sciences 18(2), 110–127 (1979). （可分指针机模型下的 Ω(m α)\Omega(m\,\alpha) 下界）
  • Tarjan, R. E. & van Leeuwen, J. "Worst-case Analysis of Set Union Algorithms." Journal of the ACM 31(2), 245–281 (1984). （各种链接策略与路径压缩组合的复杂度）
  • Fredman, M. & Saks, M. "The Cell Probe Complexity of Dynamic Data Structures." STOC, 1989.
  • Kruskal, J. B. "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proceedings of the American Mathematical Society 7(1), 48–50 (1956).
  • Rosenfeld, A. & Pfaltz, J. L. "Sequential Operations in Digital Picture Processing." Journal of the ACM 13(4), 471–494 (1966). （两遍扫描连通域标记与等价表）
  • Paterson, M. S. & Wegman, M. N. "Linear Unification." Journal of Computer and System Sciences 16(2), 158–167 (1978).
  • Holm, J., de Lichtenberg, K. & Thorup, M. "Poly-logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-edge, and Biconnectivity." Journal of the ACM 48(4), 723–760 (2001).
  • Sleator, D. D. & Tarjan, R. E. "A Data Structure for Dynamic Trees." Journal of Computer and System Sciences 26(3), 362–391 (1983).
  • Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022. （第19章 Disjoint Sets，含 Ak(j)A_k(j) 与 α(n)\alpha(n) 的定义）
  • Rust 项目 ena crate（UnificationTable：从 rustc 抽出的并查集 / 合一实现，含快照与回滚）。

延伸阅读

  • Sedgewick, R. & Wayne, K. Algorithms. 4th ed. Addison-Wesley, 2011. （第1.5章 Union-Find，含渗流实验）
  • Galil, Z. & Italiano, G. F. "Data Structures and Algorithms for Disjoint Set Union Problems." ACM Computing Surveys 23(3), 1991. （并查集各类变体的综述）
  • Pierce, B. C. Types and Programming Languages. MIT Press, 2002. （第 22 章类型重建与合一，理解编译器为何需要并查集）

正文中引用本条 · 1