第 7 章并查集

Disjoint Set Union

动态维护等价类

并查集维护一组互不相交的集合。

它支持两类操作：

find(x)：找到元素 x 所在集合的代表
union(x, y)：合并 x 和 y 所在集合

典型应用：连通性、Kruskal 最小生成树、成环检测、图像区域合并。

Linux 动态判断对象是否属于同一资源组

PostgreSQL 分区、分组和连接处理中常见集合合并思想

Neo4j 连通分量和社群预处理依赖集合合并

C++ 最小生成树、离线连通性和成环检测的标准工具

学习目标

理解等价关系如何把全集划分为互不相交的等价类
掌握 find、union、combine 的职责边界
用森林和 parent 数组表示动态集合
理解朴素实现为什么会退化成链
掌握按大小合并、按秩合并和路径压缩
能解释并查集的摊还复杂度为什么接近常数
能把并查集用于动态连通性和 Kruskal 最小生成树

路线图

等价关系

集合 \(U\) 上的关系 \(\equiv\) 若满足：

自反性：\(x\equiv x\)
对称性：若 \(x\equiv y\)，则 \(y\equiv x\)
传递性：若 \(x\equiv y\) 且 \(y\equiv z\)，则 \(x\equiv z\)

则它是等价关系。

等价关系会把全集划分为若干个互不相交的等价类。

等价类示例

全集：

\[ S=\{0,1,2,\ldots,11\} \]

等价对：

\[ (0,4),(3,1),(6,10),(8,9),(7,4),(6,8),(3,5),(2,11),(11,0) \]

这些关系会逐步把单元素集合合并成更大的等价类。

Online 操作

combine(a,b) 可以分解为：

int i = find(a);
int j = find(b);
if (i != j) {
  unite(i, j);
}

find 负责定位集合代表。

unite 只合并两个代表。

森林表示

parent 数组

每个集合是一棵树，根代表集合。

常见表示：

parent[x] == x：x 是根
parent[x] < 0：x 是根，负数记录大小或秩
parent[x] 指向父结点

森林结构只关心根代表，不关心树中兄弟顺序。

parent 数组追踪

简单实现

class DisjointSet {
 public:
  explicit DisjointSet(int n) : parent_(n) {
    std::iota(parent_.begin(), parent_.end(), 0);
  }

  int find(int x) const {
    while (parent_[x] != x) {
      x = parent_[x];
    }
    return x;
  }

  void uniteRoots(int root1, int root2) {
    parent_[root2] = root1;
  }

 private:
  std::vector<int> parent_;
};

简单版本的 find 时间是 \(O(h)\)。

最坏情况

若依次执行：

\[ union(2,1), union(3,2), union(4,3), union(5,4),\ldots \]

可能形成高度为 \(n-1\) 的链。

此时 find 最坏为：

\[ O(n) \]

优化目标是让树尽量矮。

按大小合并

规则：

记录每棵树的结点数
小树挂到大树下面
根结点保存集合大小

也可以用一个数组同时保存父指针和大小：根位置保存负大小，非根位置保存父结点下标。

void unite(int a, int b) {
  int ra = find(a);
  int rb = find(b);
  if (ra == rb) return;
  if (size_[ra] < size_[rb]) std::swap(ra, rb);
  parent_[rb] = ra;
  size_[ra] += size_[rb];
}

小树合并到大树后，任意结点深度增加次数有限。

按秩合并

秩可以近似理解为树高上界。

void unite(int a, int b) {
  int ra = find(a);
  int rb = find(b);
  if (ra == rb) return;
  if (rank_[ra] < rank_[rb]) std::swap(ra, rb);
  parent_[rb] = ra;
  if (rank_[ra] == rank_[rb]) {
    ++rank_[ra];
  }
}

只有两棵秩相同的树合并时，新根秩才增加。

路径压缩

路径压缩在 find 时把路径上的结点直接连到根。

int find(int x) {
  if (parent_[x] != x) {
    parent_[x] = find(parent_[x]);
  }
  return parent_[x];
}

一次查询会顺便改善之后的查询。

完整 C++ 实现

class DisjointSet {
 public:
  explicit DisjointSet(int n) : parent_(n), rank_(n, 0) {
    std::iota(parent_.begin(), parent_.end(), 0);
  }

  int find(int x) {
    if (parent_[x] != x) {
      parent_[x] = find(parent_[x]);
    }
    return parent_[x];
  }

  bool unite(int a, int b) {
    int ra = find(a);
    int rb = find(b);
    if (ra == rb) return false;
    if (rank_[ra] < rank_[rb]) std::swap(ra, rb);
    parent_[rb] = ra;
    if (rank_[ra] == rank_[rb]) ++rank_[ra];
    return true;
  }

 private:
  std::vector<int> parent_;
  std::vector<int> rank_;
};

复杂度

单独按大小或按秩合并，可以把树高控制到 \(O(\log n)\)。

再加路径压缩后，摊还复杂度为：

\[ O(\alpha(n)) \]

\(\alpha(n)\) 是反 Ackermann 函数，在任何实际规模下都小于 5。

运行时性能：parent 数组为什么快

并查集的核心状态是一段连续的 parent 数组。

find 反复读取父下标，访问模式比链式树更紧凑
路径压缩会把未来访问改写为更短的内存路径
按秩合并减少树高，也减少循环次数和 cache miss
连续数组比分散节点更容易被硬件预取

在操作系统和运行时层面，真正影响常数的因素包括：

parent 数组是否能留在 cache 中
路径压缩写回是否造成额外写流量
多线程场景中是否需要同步或原子操作

因此并查集的优势不只是渐近复杂度好，也来自表示方式非常贴近机器。

复杂度策略对照

应用一：动态连通性

不断加入边，并回答两个点是否连通：

DisjointSet dsu(n);
for (auto [u, v] : edges) {
  dsu.unite(u, v);
}
bool connected = dsu.find(a) == dsu.find(b);

连通块的代表由根结点表示。

应用二：Kruskal 算法

Kruskal 最小生成树：

按边权从小到大排序
依次考虑每条边
若边的两个端点不连通，则选这条边并合并集合
若已经连通，则跳过，避免形成环

并查集负责快速判断“是否成环”。

多维分析

实现	`find`	`union`	特征
简单森林	\(O(h)\)，最坏 \(O(n)\)	\(O(1)\)	可能退化
按大小合并	\(O(\log n)\)	\(O(\log n)\)	树高受控
按秩合并	\(O(\log n)\)	\(O(\log n)\)	用秩近似高度
路径压缩 + 按秩	摊还 \(O(\alpha(n))\)	摊还 \(O(\alpha(n))\)	实际近似常数

练习 1：等价类合并

对集合 \(\{0,1,2,3,4\}\) 执行：

\[ union(0,1), union(2,3), union(1,2) \]

答案：

最终等价类为：

\[ \{0,1,2,3\},\{4\} \]

练习 2：路径压缩结果

若有路径：

\[ 6\to3\to1 \]

执行 find(6) 后，路径压缩会令：

\[ parent[6]=1 \]

若递归实现完整压缩，也会保证路径上的中间结点直接指向根。

练习 3：Kruskal 中为什么需要并查集

答案：

排序后的边逐条尝试加入生成树。

如果一条边的两个端点已经属于同一集合，加入它会形成环。

若端点属于不同集合，加入它不会形成环，并且应合并这两个集合。

第 7 章 并查集