C++并查集进阶：从基础原理到路径压缩优化实战

1. 什么是并查集？

并查集是一种用于管理不相交集合的数据结构，核心应用场景是解决“动态连通性”问题。在给定一系列整数对（代表对象间的连接关系）时，我们需要判断两个对象是否属于同一个连通分量。这种连通关系具备以下等价性特征：

• 自反性：任意节点都与自身连通。
• 对称性：若 p 与 q 连通，则 q 也与 p 连通。
• 传递性：若 p 与 q 连通且 q 与 r 连通，则 p 与 r 连通。

在算法术语中，我们将对象称为“触点”，连接操作称为“Union”，而连通的子集称为“连通分量”。并查集的目标就是高效地执行合并（Union）和查找（Find）操作，以维护这些分量的状态。

2. 标准 API 设计

一个标准的并查集实现通常包含以下核心接口：UF(N) 初始化 N 个独立分量；find(p) 查找元素 p 所在分量的标识；union(p, q) 合并 p 和 q 所在的两个分量；connected(p, q) 判断两元素是否已连通；以及 count() 返回当前剩余的分量数量。

第1步：定义基础类架构

首先构建并查集的骨架，使用整型数组 id 来存储每个触点的父节点索引，并使用 count 记录当前连通分量的总数。初始状态下，每个触点都是独立的，因此 id[i] = i。

public class UF {
private int[] id; // 分量ID数组，以触点为索引
private int count; // 当前连通分量数量

public UF(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) {
id[i] = i; // 初始化每个节点指向自身
}
}

public int count() {
return count;
}

public boolean connected(int p, int q) {
return find(p) == find(q);
}

public int find(int p) {
// 具体实现取决于不同算法变体
return -1;
}

public void union(int p, int q) {
// 具体实现取决于不同算法变体
}
}

3. Quick-Find 算法

Quick-Find 的核心思想是保证同一连通分量中的所有节点在 id[] 数组中具有相同的值。这样，connected(p, q) 操作只需判断 id[p] == id[q] 即可，时间复杂度为 O(1)。

第2步：实现 Quick-Find 合并逻辑

虽然查询极快，但合并操作代价高昂。当需要合并 p 和 q 所在的两个不同分量时，必须遍历整个数组，将所有与 p 具有相同 ID 的元素修改为 q 的 ID。这导致每次合并的时间复杂度为 O(N)，在处理大规模数据时性能较差。

public class QuickFindUF {
private int[] id;
private int count;

public QuickFindUF(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;
}

public boolean connected(int p, int q) {
return id[p] == id[q]; // O(1) 查询
}

public void union(int p, int q) {
int pID = id[p];
int qID = id[q];
if (pID == qID) return; // 已在同一分量，无需合并

// 关键步骤：遍历数组，统一分量ID
for (int i = 0; i < id.length; i++) {
if (id[i] == pID) id[i] = qID;
}
count--;
}
}

4. Quick-Union 算法

为了优化合并操作的效率，Quick-Union 采用树形结构表示分量。每个节点的 id[] 指向其父节点，根节点的 id[] 指向自身。查找操作变为沿着指针向上追溯直到根节点，合并操作则是将一个树的根节点指向另一个树的根节点。

第3步：实现基于树的查找与合并

此算法大幅提升了 Union 的速度，但在最坏情况下（树退化为链），查找操作的深度可能达到 O(N)，导致整体效率不稳定。

public class QuickUnionUF {
private int[] id;
private int count;

public QuickUnionUF(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;
}

public int find(int p) {
// 沿父节点一直追溯到根
while (p != id[p]) {
p = id[p];
}
return p;
}

public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;

// 将一棵树的根连接到另一棵树的根
id[pRoot] = qRoot;
count--;
}
}

5. 加权 Quick-Union 算法

Quick-Union 的主要缺陷在于树的高度不可控。加权策略通过在合并时比较两棵树的大小（节点数），始终将较小的树附加到较大的树上。这一简单的改动确保了树的高度保持在 logN 级别，从而显著提升了算法的整体性能。

第4步：引入大小数组进行平衡合并

新增 sz[] 数组记录每个根节点下属的子树大小。在 union 操作中，根据 sz[pRoot] 和 sz[qRoot] 的关系决定链接方向，并更新根节点的大小。

public class WeightedQuickUnionUF {
private int[] id; // 父链接数组
private int[] sz; // 各根节点对应的分量大小
private int count;

public WeightedQuickUnionUF(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;

sz = new int[N];
for(int i = 0; i < N; i++) sz[i] = 1; // 初始大小为1
}

public int find(int p) {
while (p != id[p]) {
p = id[p];
}
return p;
}

public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;

// 小树挂大树，保持高度平衡
if (sz[pRoot] < sz[qRoot]) {
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
} else {
id[qRoot] = id[pRoot];
sz[pRoot] += sz[qRoot];
}
count--;
}
}

6. 带路径压缩的加权 Quick-Union

这是目前实践中最高效的并查集实现。它在保持加权平衡的基础上，进一步优化了 find 操作。路径压缩的核心思想是：在查找根节点的过程中，将路径上的所有节点直接连接到根节点，从而使树尽可能扁平化。经过多次操作后，几乎所有节点都直接指向根，几乎达到常数级时间复杂度。

第5步：实现路径压缩逻辑

路径压缩可以通过递归或迭代两种方式实现。迭代版本避免了函数调用的开销，更适合大规模数据处理。它先找到根节点，再次遍历路径将每个节点的父节点直接改为根节点。

public class PathCondenseWeightedQuickUnionUF {
private int[] id;
private int[] sz;
private int count;

public PathCondenseWeightedQuickUnionUF(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;

sz = new int[N];
for(int i = 0; i < N; i++) sz[i] = 1;
}

public int find(int p) {
// 第一步：找到根节点
int root = p;
while (root != id[root]) {
root = id[root];
}

// 第二步：路径压缩，将路径上所有节点指向根
while (id[p] != root) {
int temp = p;
p = id[p];
id[temp] = root;
}
return root;
}

// union 逻辑同加权Quick-Union
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;

if (sz[pRoot] < sz[qRoot]) {
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
} else {
id[qRoot] = id[pRoot];
sz[pRoot] += sz[qRoot];
}
count--;
}
}

7. 算法性能对比总结

对于 N 个触点和 M 次操作的场景，各算法在最坏情况下的性能增长数量级如下表所示。可以看出，加权并加上路径压缩的算法在实际应用中表现极为优异，单次操作的平均时间复杂度几乎趋近于常数。

以上就是C++并查集（Union-Find）从基础原理到路径压缩优化的详细内容，更多关于C++高级数据结构与算法优化的资料请关注本站其它相关文章！