不相交集合森林

概述

不相交集合森林（Disjoint-Set Forest）用一组有根树来表示不相交集合数据结构中的每个集合。每棵树的根节点即为集合的代表，每个节点只维护一个 parent 指针。这是实践中最高效的并查集表示方式。

定义

不相交集合森林

用一个森林（有根树的集合）来维护不相交集合的划分：

• 每个集合对应一棵有根树
• 树的根节点是集合的代表（representative）
• 每个节点 $x$ 只存储一个属性：parent[x]
• 根节点满足 parent[x] = x（自指向）
• 非根节点满足 parent[x] 指向其在树中的父节点

数据结构

集合 S_1 = {a, b, c, d}     集合 S_2 = {e, f, g}

        a                         e
       / \                       / \
      b   c                     f   g
      |
      d

parent[a] = a    (根)
parent[b] = a
parent[c] = a
parent[d] = b
parent[e] = e    (根)
parent[f] = e
parent[g] = e

核心操作的伪代码

MAKE-SET

MAKE-SET(x)
1  x.parent = x
2  x.rank = 0          // 仅在使用按秩合并时需要

• 时间复杂度：$O(1)$

FIND-SET

FIND-SET(x)
1  if x != x.parent
2      x.parent = FIND-SET(x.parent)  // 路径压缩（递归版）
3  return x.parent

• 不加路径压缩（第2行改为直接递归不修改 parent）：$O(\lg n)$（按秩合并下）
• 加路径压缩：$O(\alpha (n))$ 均摊（按秩合并下）

UNION

UNION(x, y)
1  LINK(FIND-SET(x), FIND-SET(y))

LINK

LINK(x, y)
// 前置条件：x 和 y 是不同树的根
1  if x.rank > y.rank
2      y.parent = x
3  else x.parent = y
4      if x.rank == y.rank
5          y.rank = y.rank + 1

• 时间复杂度：$O(1)$（不含 FIND-SET 的代价）

复杂度分析

不同优化组合的复杂度

优化策略	单次 FIND-SET	$m$ 次操作总复杂度	说明
无优化	$O(n)$ 最坏	$O(mn)$	树可能退化为链
按秩合并	$O(\lg n)$	$O(m\lg n)$	树高 $\le \lfloor \lg n\rfloor$
按秩合并 + 路径压缩	$O(\alpha (n))$ 均摊	$O(m\alpha (n))$	接近 $O(1)$ 的最优复杂度

为什么森林优于链表

1. UNION 更快：LINK 操作 $O(1)$，无需更新大量指针
2. 空间更省：每个节点只需一个 parent 指针（加 rank 两个字段），链表需要 set 指针 + 链表指针
3. 缓存友好：节点结构紧凑，内存访问模式更优

核心性质

森林的关键不变式

• 代表不变式：FIND-SET(x) 总是返回 $x$ 所在树的根节点
• 根的自指向：对根节点 $r$，parent[r] = r
• 树的唯一性：每棵树恰好对应一个集合，不同集合的树之间没有边相连

路径压缩的效果

路径压缩不改变树的有根性质，但会”压扁”从节点到根的路径，使后续 FIND-SET 更快。注意路径压缩可能破坏按秩合并维护的秩的精确含义（秩变为高度的上界而非精确高度）。

参见

• 不相交集合数据结构 — 并查集的总览与三种核心操作
• 按秩合并 — LINK 操作中的合并策略
• 路径压缩 — FIND-SET 中的路径优化
• 反阿克曼函数 — $O(m\alpha (n))$ 复杂度中的关键函数
• 加权合并启发式 — 链表表示中的类似优化思想