数据结构与算法 / 系统课时
并查集到底维护什么
并查集到底维护什么
并查集解决的不是“两个点之间具体怎么走”,而是“两个元素是否属于同一个连通集合”。理解代表元、parent、find 与 union 的职责后,就能把动态连通问题转化为集合合并与代表元查询。
学习目标
- 理解并查集维护的是互不相交集合及其代表元
- 掌握
parent、find、union三者之间的语义关系 - 能用最小实现判断两个元素是否已经连通
并查集维护的是集合归属
假设有 5 个节点,开始时彼此都不连通,可以把它们看成 5 个独立集合。并查集为每个集合选择一个代表元,也称根。两个节点的代表元相同,就说明它们属于同一个集合。
parent[x] 记录节点 x 当前指向的父节点。根节点满足 parent[x] == x。这些父指针组成若干棵树,每棵树对应一个互不相交集合;树的根就是这个集合的代表元。

这里维护的是集合身份,而不是图中的真实边。即使原图中 2 通过 1 才能到达 0,并查集也只关心它们最终是否拥有同一个代表元,因此特别适合连通性判断,而不适合恢复实际路径。
find 找到集合代表元
find(x) 沿着 parent 不断向上查找,直到遇到父节点等于自己的根。返回值就是 x 所属集合的代表元。
例如 parent = [0, 0, 1, 3, 4] 时,节点 2 的查找过程是 2 → 1 → 0,所以 find(2) 返回 0。只要两个节点的 find 结果相等,它们就已经连通。
union 合并两个集合
union(a, b) 并不是直接令 parent[a] = b。正确做法是先分别找到两个集合的根,再把其中一个根连接到另一个根。这样才能保证合并的是完整集合,而不是只改变某个局部节点。
下面是一个不带优化、但语义完整的最小 Python 实现:
class DisjointSet:
def __init__(self, n: int):
self.parent = list(range(n))
def find(self, x: int) -> int:
# 沿父指针一直找到代表元。
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, a: int, b: int) -> bool:
root_a = self.find(a)
root_b = self.find(b)
if root_a == root_b:
return False
# 只有根节点之间发生连接,才能合并整个集合。
self.parent[root_b] = root_a
return True
def connected(self, a: int, b: int) -> bool:
return self.find(a) == self.find(b)
dsu = DisjointSet(5)
dsu.union(0, 1)
dsu.union(1, 2)
print(dsu.parent)
print(dsu.connected(0, 2))
print(dsu.connected(0, 4))预期输出
[0, 0, 0, 3, 4]
True
False这个结果说明 0、1、2 已经归入同一集合,而 4 仍然独立。实际实现通常还会加入路径压缩和按秩或按大小合并,以避免父指针树不断变深。
什么时候适合使用并查集
并查集最适合处理“不断增加连接,并反复询问是否连通”的问题,例如动态加入网络连接、判断无向图新增边是否形成环、计算连通分量,以及 Kruskal 最小生成树中的环检测。
它不擅长删除连接,也不会保存两点之间的实际路径。如果问题要求最短路径、经过哪些节点,或者边会频繁删除,就需要 BFS、DFS、最短路算法或更复杂的动态连通数据结构,而不能只依赖并查集。