并查集快速合并：从零理解数据结构中的“高效连接”
你有没有遇到过这样的场景：在社交网络中判断两个人是否属于同一个朋友圈？在文件系统中判断两个路径是否在同一个目录结构下？或者在图论中快速判断两个节点是否连通？这些看似不同的问题，其实都可以用一个高效的数据结构来解决——并查集（Union-Find）。
今天我们就来深入聊聊“并查集快速合并”这个核心思想。它不仅在算法面试中频繁出现，更在实际工程中扮演着重要角色。别担心，我会用最直观的方式，带你一步步掌握它的原理和应用。
什么是并查集？它能解决什么问题？
并查集是一种用来管理不相交集合（Disjoint Sets）的数据结构。它的核心操作只有两个：
- 合并（Union）：把两个集合合并成一个。
- 查询（Find）：判断两个元素是否属于同一个集合。
举个生活中的例子：想象你有一堆散落的纸条，每张纸条上写着一个人的名字。你每天都会遇到新朋友，并决定是否把他们“归为一类”——比如，你和小明是朋友，小明和小红是朋友，那你们三个人自然就属于同一个朋友圈。
并查集就是帮你快速判断“小明和小红是不是同一圈人”，以及“要不要把小李也拉进来”的工具。
创建数组与初始化
要实现并查集，最常用的方法是用一个数组 parent[] 来记录每个元素的“父节点”。初始时，每个元素都指向自己，表示它是一个独立的集合。
比如，有 5 个人：0, 1, 2, 3, 4。我们创建一个长度为 5 的数组：
parent = [0, 1, 2, 3, 4]
这时候，每个节点都是自己所在的集合的“根”。
| 索引 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| parent | 0 | 1 | 2 | 3 | 4 |
这个状态表示：五个独立的人，还没开始“社交”。
如何实现“快速合并”？路径压缩的智慧
我们先来实现最基本的合并操作。假设我们要把 0 和 1 合并，那么只需要让 1 的父节点指向 0 即可。
def union(parent, x, y):
# 找到 x 和 y 的根节点
root_x = find(parent, x)
root_y = find(parent, y)
# 如果已经在同一个集合，无需合并
if root_x == root_y:
return
# 将 root_y 的父节点设为 root_x，完成合并
parent[root_y] = root_x
但问题来了：如果不断合并，树结构会变得越来越“高”，比如：
0 → 1 → 2 → 3 → 4
这时候，每次 find(4) 都要走 4 步，效率会下降。
怎么办？引入路径压缩（Path Compression）！
在 find 操作中，我们把沿途的所有节点都直接指向根节点，让树“扁平化”。
def find(parent, x):
# 如果 x 不是根节点，递归查找根，并压缩路径
if parent[x] != x:
parent[x] = find(parent, parent[x]) # 递归压缩路径
return parent[x]
举个例子：当 find(4) 被调用时，我们发现 parent[4] = 3，于是递归调用 find(3)，直到找到根节点 0，然后回溯时把 3、4 的父节点都直接设为 0。
这样，下次再查 4，只需一步就到根。
优化合并策略：按秩合并（Union by Rank）
仅仅路径压缩还不够。想象一下，我们总是把小树合并到大树上，虽然能合并，但树的高度增长仍然很快。
我们可以用“按秩合并”来优化：每次合并时，把秩小的树合并到秩大的树上，从而保持树的平衡。
秩（Rank）表示树的高度的近似值。初始时，所有节点的秩都是 0。
def union_by_rank(parent, rank, x, y):
root_x = find(parent, x)
root_y = find(parent, y)
if root_x == root_y:
return
# 按秩合并：将秩小的树合并到秩大的树上
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
# 秩相等时，随便合并，并增加新根的秩
parent[root_y] = root_x
rank[root_x] += 1
配合路径压缩，这种策略能让并查集的性能接近 O(1) 的均摊时间复杂度。
实际案例：岛屿数量问题（LeetCode 200）
让我们用一个经典题目来实战“并查集快速合并”。
题目：给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿是由水平或垂直方向相邻的陆地连接而成的区域。
我们可以把每个 '1' 看作一个节点，相邻的陆地之间进行合并。
def numIslands(grid):
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
# 初始化 parent 和 rank 数组
parent = list(range(rows * cols))
rank = [0] * (rows * cols)
# 方向数组：上下左右
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # 路径压缩
return parent[x]
def union(x, y):
root_x = find(x)
root_y = find(y)
if root_x == root_y:
return
# 按秩合并
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
# 遍历每个格子
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
index = i * cols + j
# 检查四个方向的邻居
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1':
neighbor_index = ni * cols + nj
union(index, neighbor_index)
# 统计根节点的数量，即岛屿数量
roots = set()
for i in range(rows * cols):
if grid[i // cols][i % cols] == '1':
roots.add(find(i))
return len(roots)
这个算法的时间复杂度接近 O(MN × α(MN))，其中 α 是阿克曼函数的反函数，增长极慢，几乎可以视为常数。
为什么“并查集快速合并”如此高效？
我们来总结一下“并查集快速合并”背后的三个核心优化：
- 路径压缩：在查找时扁平化路径，让后续查找更快。
- 按秩合并：避免树过深，保持结构平衡。
- 合并即连接：不关心具体结构，只关心“是否连通”。
这两个优化组合起来，使得并查集在实际应用中表现极为出色。哪怕处理百万级别的数据，也能在毫秒内完成。
常见误区与注意事项
- 不要忘记初始化：parent 数组必须初始化为
i，否则会出错。 - 合并前先查根：必须先用
find找到根节点，再合并。 - 路径压缩的递归写法：虽然简洁，但在极端情况可能栈溢出。可改为迭代版本。
- 秩的更新时机：只有在两棵树秩相等时才需要增加新根的秩。
总结：掌握并查集，提升算法思维
并查集快速合并，本质上是一种“用空间换时间”的智慧设计。它不追求最完美的结构，而是通过简单的规则（路径压缩 + 按秩合并），在实践中实现了接近线性的时间复杂度。
无论你是准备面试的开发者，还是在做图论、网络分析的工程师，掌握并查集都能让你在处理“连通性”问题时更加得心应手。
下次当你遇到“判断是否连通”“合并集合”“统计连通分量”这类问题时，别再用 DFS/BFS 暴力搜索了——试试并查集快速合并，你会发现效率提升不止一倍。
记住：算法不是记住代码，而是理解思想。并查集就是这样一个思想的典范。