并查集路径压缩：让数据结构跑得更快的秘密武器
你有没有遇到过这样的场景？在处理大量“集合合并”和“连通性判断”的问题时，程序运行越来越慢，哪怕数据量只是稍微增加一点，响应时间就翻倍？这背后，往往是因为我们没有使用最合适的算法结构。
今天要聊的，就是解决这类问题的利器——并查集（Union-Find）。而其中最核心、最高效的优化技巧，正是“路径压缩”。它能让原本可能很慢的操作，瞬间变得飞快，甚至达到接近常数时间的性能。
别担心，我们不会一上来就堆概念。先从一个生活中的例子说起。
什么是并查集？它能解决什么问题？
想象你正在玩一款多人联机游戏，每个玩家属于一个战队。当两个玩家组队时，系统需要判断他们是否已经在同一个战队里。如果不在，就合并战队。这种“判断是否连通”“合并集合”的操作，就是并查集最擅长的场景。
在算法世界里，这类问题被称为“动态连通性问题”——集合的连接状态是动态变化的，我们需要实时维护这些状态。
并查集的核心功能有两个：
union(a, b)：把元素 a 和 b 所在的集合合并find(a)：找出元素 a 所在集合的代表元（根节点）
举个例子，假设我们有 5 个元素：1、2、3、4、5。初始时每个元素各自独立成一个集合。
parent = [0, 1, 2, 3, 4, 5] # 下标从 1 开始，parent[1] = 1 表示 1 是自己的根
如果执行 union(1, 2)，就把 1 和 2 合并，比如让 2 成为 1 的父节点：
parent[1] = 2 # 现在 1 的父节点是 2
再执行 union(2, 3)，让 3 的父节点也变成 2：
parent[3] = 2
此时，1、2、3 都连通了，它们的根都是 2。
普通并查集的效率问题：树越深，查找越慢
我们来思考一个问题：find(1) 是怎么执行的？
def find(x):
while parent[x] != x:
x = parent[x]
return x
这个过程很简单：从 x 开始，一直往上找父节点，直到找到根节点（即 parent[x] == x）。
但问题来了：如果链太长，比如 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8，那么 find(1) 要走 7 步才能到根。
想象一下，如果你有成千上万个元素，这种“长链”会越来越多，查找效率会急剧下降。最坏情况下，时间复杂度会退化到 O(N)，这显然无法接受。
这就是为什么我们需要“路径压缩”——它能让我们在查找过程中，把“长路径”直接压平，让所有节点都直接指向根。
路径压缩：让查找路径变成“高速公路”
路径压缩的核心思想是：在查找根节点的过程中，把沿途的所有节点都直接连到根节点上。
这样，下次再找这些节点，就不用走长路了。
递归实现路径压缩
def find(x):
# 如果 x 的父节点不是自己，说明还没到根
if parent[x] != x:
# 递归找到根节点，并将 x 的父节点直接设为根
parent[x] = find(parent[x])
return parent[x]
让我们一步步看 find(1) 的过程：
parent[1] = 2，不是根，进入递归find(2)：parent[2] = 2，是根，返回 2- 回到
find(1)，执行parent[1] = find(2)→parent[1] = 2 - 返回 2
此时，1 直接指向根 2，路径被压缩了！
迭代实现路径压缩（更高效）
递归虽然清晰，但可能栈溢出。我们可以用迭代方式实现路径压缩：
def find(x):
root = x
# 先找到根节点
while parent[root] != root:
root = parent[root]
# 再从 x 开始，把所有路径上的节点都指向根
while parent[x] != x:
next_node = parent[x]
parent[x] = root
x = next_node
return root
这段代码先找到根，再回头把所有中间节点的父节点改为根。这种“两次遍历”的方式，避免了递归，性能更稳定。
路径压缩的实际效果：从 O(log N) 到近乎 O(1)
我们来对比一下两种方式的效率：
| 操作 | 普通并查集（无路径压缩） | 带路径压缩的并查集 |
|---|---|---|
find 时间复杂度 |
O(log N) 或更高 | O(α(N))，α 是阿克曼函数的反函数 |
union 时间复杂度 |
O(log N) | O(α(N)) |
| 实际运行速度 | 慢，长链影响大 | 极快，几乎常数时间 |
注意：α(N) 增长极其缓慢。比如：
- α(10^100) ≈ 5
也就是说，哪怕你有 10^100 个元素，路径压缩后的并查集，平均查找也只需要 5 步！这已经接近常数时间。
一个完整案例：岛屿数量问题
我们用一个经典问题来实战路径压缩的价值。
问题描述：给定一个 m×n 的二维网格，每个格子是 '1'（陆地）或 '0'（水）。求岛屿的数量。岛屿由四连通的陆地组成。
解法思路
- 把每个陆地格子看作一个节点
- 如果两个陆地格子上下左右相邻，就进行
union操作 - 最后统计有多少个不同的根节点，就是岛屿数
代码实现（含路径压缩）
class UnionFind:
def __init__(self, m, n):
# 总共 m * n 个格子，用一维数组表示
self.parent = [i for i in range(m * n)]
self.rank = [0] * (m * n) # 用于按秩合并，进一步优化
self.count = m * 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):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return # 已经连通，无需合并
# 按秩合并：小树挂到大树下
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
self.count -= 1 # 合并成功，集合数减一
def get_count(self):
return self.count
def numIslands(grid):
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
uf = UnionFind(m, n)
# 四个方向：上下左右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
# 将二维坐标转为一维
idx = i * n + j
# 检查四个方向的邻居
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == '1':
nidx = ni * n + nj
uf.union(idx, nidx)
return uf.get_count()
关键点说明
find中使用了递归路径压缩，代码简洁，效果显著union中加入了“按秩合并”，与路径压缩配合，能进一步提升性能- 时间复杂度：O(MN × α(MN))，空间复杂度：O(MN)
在这个例子中，如果不用路径压缩，当网格很大时，find 操作可能反复遍历长链，导致超时。而路径压缩让整个算法稳定高效。
如何判断是否需要路径压缩？
你可以在以下情况优先考虑使用路径压缩：
- 需要频繁进行
find操作（如 10^5 次以上） - 数据规模大（元素数 > 10^4）
- 有大量
union操作，导致树结构容易变深 - 在竞赛、面试或生产系统中对性能敏感
路径压缩的代价极低，但收益极高。几乎没有任何理由不使用它。
总结：路径压缩是并查集的灵魂
并查集本身是一个非常优雅的数据结构，而路径压缩，正是让它从“可用”变为“高效”的关键。
它就像一条高速公路，把原本蜿蜒曲折的路径直接拉直，让每个节点都能“一步到位”找到根。
无论你是初学者，还是正在准备面试的开发者，掌握路径压缩，不仅能让你写出更高效的代码，更能深刻理解算法优化的本质：不是一味追求复杂，而是通过巧妙的重构，让数据结构“自己变快”。
下次当你遇到“连通性”“集合合并”类问题时，别忘了带上你的“路径压缩”武器——它会让你的程序跑得更快，也让你的算法思维更上一层楼。