路径压缩

概述

路径压缩（Path Compression）是不相交集合森林中 FIND-SET 操作的优化策略。在查找元素 $x$ 所在集合的代表时，使从 $x$ 到根的路径上的所有节点直接指向根，从而”压扁”路径，加速后续查询。

定义

路径压缩

在执行 FIND-SET(x) 时，在找到 $x$ 所在树的根 $r$ 之后，将 $x$ 到 $r$ 路径上的每个节点的 parent 指针直接设置为 $r$。

效果：原本长度为 $h$ 的路径被压缩为长度 1（所有节点直接连到根）。

路径压缩示意图

压缩前：                压缩后（FIND-SET(d)）：

      r                      r
    / | \                  / | \ | \
   a  b  c    ──→        a  b  c  d  e
  / \                    |
 d   e                   (d 和 e 原本在路径上，现在直接指向 r)

两种实现方式

递归实现（简洁）

FIND-SET(x)
1  if x != x.parent
2      x.parent = FIND-SET(x.parent)  // 递归查找 + 路径压缩
3  return x.parent

• 第 2 行先递归找到根，然后在回溯过程中逐层将 parent 指向根
• 代码简洁，但递归深度可能达到 $O(\lg n)$，极端情况下可能栈溢出

迭代实现（避免栈溢出）

FIND-SET(x)
1  root = x
2  while root != root.parent      // 第一步：找到根
3      root = root.parent
4  while x != x.parent            // 第二步：路径压缩
5      next = x.parent
6      x.parent = root
7      x = next
8  return root

• 第一轮循环（第 2-3 行）找到根节点
• 第二轮循环（第 4-7 行）将路径上所有节点的 parent 直接指向根
• 不使用递归，无栈溢出风险

核心性质

单独使用路径压缩

路径压缩的独立效果

单独使用路径压缩（不配合按秩合并）时：

• 最坏情况下，$m$ 次操作的复杂度为 $O(m\lg n)$
• 存在构造的 adversarial 序列使得树高达到 $\Omega (\lg n)$
• 路径压缩本身不能保证 $O(\alpha (n))$ 的均摊复杂度

与按秩合并结合

关键定理

**同时使用路径压缩和按秩合并**时，对 $n$ 个元素执行 $m$ 次 MAKE-SET、UNION、FIND-SET 操作的序列，总时间为 $O(m\alpha (n))$，其中 $\alpha (n)$ 是反阿克曼函数。

这是并查集的最优复杂度，由 Tarjan 于 1975 年证明。

路径压缩对秩的影响

秩不再精确

使用路径压缩后，rank[x] 不再精确等于以 $x$ 为根的子树高度，而是变为高度的上界。这是因为路径压缩可能缩短某些子树的高度，但 LINK 操作不会减小秩。

然而，以下性质仍然成立：

• rank[x] ≤ ⌊lg n⌋（秩的上界不变）
• 沿 parent 指针路径，秩非递减（不再严格递增）

直观理解

路径压缩的直觉类似于”缓存”：每次查找都把沿途的信息”记住”（直接指向根），这样下次查找同一子树中的任何节点时，路径都会更短。

与加权合并启发式的类比：

• 加权合并启发式控制 UNION 的代价（类似”合并时尽量少做事”）
• 路径压缩控制 FIND-SET 的代价（类似”查找时顺便整理结构”）
• 两者结合，互相补充，达到最优效果

第21章：最小生成树

Kruskal算法中使用路径压缩优化并查集的 FIND-SET 操作。在判断边的两个端点是否在同一连通分量时，路径压缩使后续查询更快。与按秩合并结合使用时，每次操作的均摊成本为 O(α(V))。

参见

• 不相交集合森林 — 森林表示的总览与操作伪代码
• 按秩合并 — 与路径压缩结合达到最优复杂度的合并策略
• 反阿克曼函数 — $O(m\alpha (n))$ 复杂度中的关键函数
• 势能方法 — 证明 $O(m\alpha (n))$ 上界使用的分析方法