并查集：连通性判定与路径压缩
并查集：连通性判定与路径压缩
并查集是一种用于管理元素分组关系的高效数据结构，核心功能是动态维护集合的合并与查询。在网络连通、图像分割、最小生成树等场景中，它都能用极低的时间代价回答“这两个节点是否连通”。本教程聚焦其核心机制——路径压缩，帮助你从原理到代码彻底掌握。
什么是并查集
并查集维护一个由若干不相交集合组成的森林。每个集合用一棵树表示，树的根节点代表该集合的“代表元素”。并查集仅提供两个基础操作：
- 查找 (Find)：确定元素属于哪个集合，即找到其所在树的根。
- 合并 (Union)：将两个元素所在的集合合并为一棵树。
正是这两个操作支撑了连通性判定：查询时，只需判断两个元素的根是否相同。
基础数据结构
并查集通常使用数组实现。假设有 n 个元素编号 0 到 n-1，数组 parent 记录每个元素的父节点。
初始化：最初每个元素自成一个集合，也就是自己指向自己。
parent = [i for i in range(n)]
此时，森林由 n 棵单节点树构成。
查找操作 (Find)
查找的目标是沿父指针一直向上走，直到遇到根节点（父节点指向自身）。
朴素实现：
def find(x):
while parent[x] != x:
x = parent[x]
return x
最坏情况下，树可能退化成链表，单次查找时间复杂度 O(n)。需要优化。
路径压缩：查找即扁平化
路径压缩是并查集的核心优化，思想极其直观：在查找过程中，将沿途遇到的所有节点直接指向根节点。这样做不仅找到了根，还大幅缩短了树的高度，让后续查询几乎变成常数时间。
实现只需在朴素查找的基础上稍作修改：
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # 递归压缩路径
return parent[x]
递归版本简洁，但需注意递归深度。若担心栈溢出，可改用迭代+路径重定向：
def find(x):
root = x
while parent[root] != root:
root = parent[root]
# 第二次遍历，将所有节点直接挂到根
while x != root:
nxt = parent[x]
parent[x] = root
x = nxt
return root
无论哪种实现，效果相同：路径上的节点从此直连根，树高几乎恒定为 1。
合并操作 (Union)
合并需要先找到两个元素各自的根，然后将其中一个根指向另一个。
def union(x, y):
root_x = find(x)
root_y = find(y)
if root_x != root_y:
parent[root_x] = root_y # 简单合并
简单的合并可能导致树高增加。配合路径压缩，即使不加额外优化，平均性能已经极好。
进阶优化：按秩合并
为了让树更平衡，引入“秩”的概念。秩可粗略理解为树高的上界。合并时始终将秩较小的树连接到秩较大的树上，若秩相等则任选并增加秩。
rank = [0] * n
def union(x, y):
rx = find(x)
ry = find(y)
if rx == ry:
return
if rank[rx] < rank[ry]:
parent[rx] = ry
elif rank[rx] > rank[ry]:
parent[ry] = rx
else:
parent[ry] = rx
rank[rx] += 1
同时应用路径压缩和按秩合并的并查集，单次操作的摊还时间复杂度接近 O(α(n))，其中 α 为反阿克曼函数，实际应用中可以视为常数时间。
连通性判定流程
连通性判定仅需两步：
- 预先将已知连通的点对进行
union。 - 对任意查询
(a, b)，返回find(a) == find(b)。
示例：给定 5 个节点的边 (0,1), (1,2), (3,4)，问 0 和 2 是否连通？0 和 3 呢？
n = 5
parent = list(range(n))
edges = [(0,1), (1,2), (3,4)]
for u, v in edges:
union(u, v)
print(find(0) == find(2)) # True
print(find(0) == find(3)) # False
即使有百万节点，判断连通也只需近乎 O(1) 时间。
复杂度直观理解
| 优化组合 | 单次操作平均时间 |
|---|---|
| 无优化 | O(n) |
| 仅路径压缩 | O(log n) 摊还 |
| 仅按秩合并 | O(log n) |
| 路径压缩 + 按秩合并 | O(α(n)) ≈ O(1) |
在生产环境中，仅实现路径压缩往往足够快，且代码更短。严谨场景建议两者并用。
典型应用场景
- 图中连通分量：遍历所有边进行合并，最终不同的根个数即连通分量数。
- 动态连通性检测：边不断加入，随时查询两点连通性。
- 最小生成树 (Kruskal 算法)：判断加入某边是否会形成环，若不会则合并并加入。
- 网络冗余 / 社交网络好友关系：圈子合并与归属查询。
- 等式与不等式矛盾判断：变量相等关系用并查集，不等关系检查是否在同一集合。
完整代码示例 (Python)
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return
if self.rank[rx] < self.rank[ry]:
self.parent[rx] = ry
elif self.rank[rx] > self.rank[ry]:
self.parent[ry] = rx
else:
self.parent[ry] = rx
self.rank[rx] += 1
def connected(self, x, y):
return self.find(x) == self.find(y)
总结
并查集用极其精简的数组结构解决了集合归属与连通性判定的难题。它的核心在于两点：
- 路径压缩让查找过程顺便“修理”树结构，使树趋向扁平。
- 按秩合并引导树平衡生长，避免退化。
两者结合后，每个操作几乎都在常数时间内完成。掌握并查集，你就拥有了处理大规模连通性问题的利器。