外观
16 - 并查集:如何快速判断两个对象是否属于同一组
前置阅读:17 - 图的 DFS 与 BFS中的图表示与连通分量概念。
本文中的“动态”只指连接不断增加;删除边后的通用动态连通不属于普通并查集能力。
摘要
假设对象 0 与 1 已连接,随后又连接了 1 与 2。此时即使 0 与 2 没有直接连接,它们也属于同一组。连接不断增加时,如果只关心“是否同组”,就可以用并查集维护分组,而不必在每次查询时重新遍历所有连接。
本文先解释并查集怎样表示集合,再说明合并与查询为什么正确,以及两种优化如何减少查找成本。账号合并、无向网络连通和朋友圈分组都可以采用这个模型,但前提是业务关系能够按“同组”处理。
1. 两个核心操作
并查集(Union-Find)维护若干互不重叠的集合:每个元素恰好属于一个集合,集合可以合并。对于无向图,这样的一组可以表示一个连通分量,即组内任意两点都能沿边互相到达、且不能再加入其他可达节点的集合。
代码用数组 parent 保存每个元素的父节点编号。沿父节点不断向上,最终到达满足 parent[root] == root 的节点,这个节点叫根节点,用来代表整个集合。一个集合表示成一棵树,多棵互不相交的树合起来叫森林。这些父子关系只是集合的内部表示,不是原始网络中的边。
初始时每个元素独立成组,所以 parent[i] = i。合并两组时,只要让一个根指向另一个根,原来两棵树中的所有元素就会到达同一个根,不必逐个修改成员。
find(x):沿父节点找到x所属集合的代表根节点。union(a, b):先查找两者的根;根不同才合并,返回true,根相同则返回false。connected(a, b):比较两者的根是否相同,判断是否同组。
下面是没有运行入口的基础类。size[root] 记录根所代表集合的元素数,用于决定合并方向;非根节点的 size 不再作为集合大小读取。输入要求 n >= 0,元素编号在 0 到 n - 1 之间,代码没有另加参数校验。
java
class UnionFind {
private final int[] parent;
private final int[] size;
UnionFind(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) return false;
if (size[rootA] < size[rootB]) {
int tmp = rootA;
rootA = rootB;
rootB = tmp;
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
return true;
}
boolean connected(int a, int b) {
return find(a) == find(b);
}
}2. 为什么需要两种优化
find 的成本取决于到根要走多少步。若总把现有大树的根挂到一个新节点下,树可能逐渐变成链,查询链尾就要经过很多父节点。
按大小合并让小集合的根挂到大集合的根下。只有小树中的节点深度可能增加;每增加一次,它们所在集合的大小至少翻倍,因此这种合并方式能限制树高。另一种做法是按秩合并:用秩作为树高的上界指标,优先把低秩树挂到高秩树下;路径压缩后,秩不一定等于实际树高。本文代码使用的是按大小合并。
路径压缩在查找根之后,把查询路径上的节点直接挂到根下。比如 4 → 3 → 0,查找 4 后变成 4 → 0,下次查询就少走一步。基础类在递归返回时完成这个修改,第 5 节则用两遍循环实现。
两种优化分别控制合并时的树高、缩短已有的查询路径。结合使用时,通常用 O(m α(n)) 描述 n 个元素上 m 次操作的总成本,其中 α(n) 是反阿克曼函数,增长极慢,因此常说每次操作“接近常数时间”。这里说的是摊还复杂度,即把一串操作的总成本分摊到每次操作,不能理解为每一次 find 都只走固定步数。若单独计算构造数组的成本,初始化还需要 O(n) 时间;两份数组占用 O(n) 空间。这些是复杂度分析,不是延迟实测。
3. 账号合并
假设业务已经规定:同一账号记录中的邮箱属于同一用户,多条记录共享邮箱时也应归为同一用户。在这个前提下,可以分三步处理:
- 用
Map将每个不同邮箱映射到唯一的整数编号,重复邮箱复用编号。 - 对每条账号记录,把第一个邮箱与其余邮箱依次执行
union。不必对所有邮箱两两合并,因为通过第一个邮箱已能连成一组。 - 遍历全部邮箱,调用
find,按根编号收集到结果分组。
例如两条记录分别包含 [a, b] 和 [b, c](这里用字母代指邮箱),共享的 b 会把 a、b、c 合为一组。根编号取决于合并过程,只是算法内部的代表,不应直接当作稳定的用户 ID。
并查集只负责分组。邮箱到用户信息的映射仍需额外 Map;姓名冲突、信息保留规则等也要由业务决定。如果共享邮箱不能证明是同一用户,就不能直接采用上述合并规则。下面的完整示例演示整数分组基础,没有实现邮箱映射和用户信息合并。
4. 不适合什么
并查集适合只增加连接的增量场景;既可以逐条处理到来的连接,也可以离线处理已收集的连接。普通并查集只记录集合的合并结果,没有保留足够的边信息来判断删边后是否仍有另一条路径。因此它不能直接在删边后拆分集合。需要频繁删边时,应考虑其他动态连通结构,或保留原图后重新计算。
它也不保存两点之间的实际路径,不能回答最短路径、路径边数或经过哪些节点。connected(a, b) 只说明两点属于同一连通分量,不能证明两点之间有直接边。对有向关系,它也不能判断指定方向上的可达性;把有向边直接用于 union 会丢失方向信息。
5. 完整可运行示例:连通分量与账号合并基础
下面的完整类对应文件名 UnionFindDemo.java,只使用 Java 基础语法和数组,无外部依赖。UF 对应前面的 UnionFind,另用 components 记录当前集合数:初始为 n,每次成功合并减 1。find 改为迭代写法,避免递归查找占用调用栈。
两份实现都要求合法编号,且没有并发访问保护。
java
/**
* 可运行示例:并查集:如何快速判断两个对象是否属于同一组。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class UnionFindDemo {
static class UF {
final int[] parent, size;
int components;
UF(int n) {
parent = new int[n];
size = new int[n];
components = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
int root = x;
// 第一遍沿父指针找到集合代表,根节点满足 parent[root] == root。
while (root != parent[root]) root = parent[root];
// 第二遍把查询路径上的节点直接挂到根上,压缩后续查询路径。
while (x != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
boolean union(int a, int b) {
int x = find(a),
y = find(b);
if (x == y) return false;
// 始终让小树挂到大树,避免合并结果退化成长链。
if (size[x] < size[y]) {
int t = x;
x = y;
y = t;
}
parent[y] = x;
size[x] += size[y];
// 两个不同集合合并后,连通分量数量减少一个。
components--;
return true;
}
boolean connected(int a, int b) {
return find(a) == find(b);
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
UF uf = new UF(6);
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
System.out.println(uf.connected(0, 2));
System.out.println(uf.connected(0, 4));
uf.union(2, 4);
System.out.println("components=" + uf.components);
}
}手工推演
按 main 中的 6 个元素推演,初始每个元素各自成组。执行前三次合并后,分组为 {0, 1, 2}、{3, 4}、{5},此时 components = 3。所以 connected(0, 2) 为 true,connected(0, 4) 为 false。
执行 union(2, 4) 时,两者的根分别是 0 和 3,集合大小分别是 3 和 2,于是 3 挂到 0 下,集合数减为 2。剩下的两组是 {0, 1, 2, 3, 4} 和 {5}。三行预期输出依次为 true、false、components=2,并非实测输出。
此时 4 的父节点仍是 3,路径为 4 → 3 → 0。若再调用 find(4)(main 中没有这一步),第二遍循环会把 parent[4] 改成 0。这才展示了路径压缩如何缩短后续查询;已经直接连到根的节点不会因此再缩短路径。
正确性依赖两个不变量,即每次操作后都应保持的条件:每个集合都表示为一棵树,其根的父节点是自身;两个元素属于同一集合,当且仅当根相同。union 只连接两个不同的根,才能合并整组且不形成父指针环。路径压缩把节点改挂到原来的根,按大小合并选择两组的连接方向,两者都不改变应有的集合成员关系。
6. 验证与排障
- 将小型无向图的并查集结果与 DFS/BFS 连通分量结果做差分测试,即用另一种实现对照相同输入的结果;
- 每次成功合并后,分量数应恰好减少 1;重复合并和自连接不应改变分量数;
- 检查每个根满足
parent[root] == root,且非根节点最终可到达根; - 延迟异常时记录
find路径长度,确认是否遗漏按秩/大小合并或路径压缩; - 标识映射错误时,重点核对业务 ID 到连续整数编号的生命周期和去重规则。
还应覆盖重复合并、自连接、孤立节点、全部连通和非法下标。合法的重复合并与自连接返回 false;n = 0 时没有合法元素编号,构造后集合数为 0;负数规模或越界编号没有自定义处理,会在数组创建或访问时触发异常。现有 main 不覆盖全部边界,也没有性能测量。
本文两份实现都不是线程安全的,而且 find 的路径压缩也会写数组。只给 find 加锁,不能保证 union 中“查根、判断、修改父节点、更新大小”的整个过程不可被其他线程打断,这种整体执行要求叫原子性。生产中应根据并发模型选择串行化、分片或专用实现;分片时还需明确跨分片合并如何协调。
7. 容易踩的坑
union时连接普通节点,可能只移动部分成员,或形成父指针环;应连接两个不同的根。- 把
size更新到非根节点,导致后续无法按实际集合大小选择合并方向。 - 在缺少树高控制、树已退化时使用递归
find,可能因调用栈过深失败;迭代可以避免这一栈风险,但仍需控制查找路径长度。 - 把“同一集合”误当成存在直接边,或把父指针当成原图路径。
- 同一业务标识被分配不同编号,或不同标识误用同一编号,导致漏合并或误合并。
- 需要删除边或恢复实际路径,却没有保留原图,只保存了并查集。
8. 总结
并查集用森林表示分组,用根节点代表集合;它维护的是分组结果,而不是完整的图。
find查询代表,union合并代表。- 按大小合并控制树高,路径压缩缩短查询路径,“接近常数”指摊还成本。
- 它适合增量连通,不天然支持删除连接后的拆分。
遍历、路径和删边后重算请阅读图的 DFS 与 BFS;依赖方向问题继续阅读拓扑排序与依赖编排。