并查集Union-Find数据结构

可视化演示

交互展示并查集的合并与查找操作，路径压缩与按秩合并优化策略，以及在Kruskal最小生成树中的应用。

基本概念

村口有两个年轻人，一个说自己是大房的，一个说是二房的。只要两房最后都归到同一个老祖宗门下，那就是一家人；但如果一个姓林的跑到姓陈的祠堂里去认亲，那就乱套了。这个生活场景告诉我们，整个世界被分成了许多互不相交的“家族”，每个人只能属于一个家族。这些家族就是数学里说的“不相交集合”。

并查集正是用来维护这些不相交集合的数据结构。它把问题抽象成两个动作：查询某个元素属于哪个集合，以及把两个集合合并成一个。查询时，我们关心的是“代表元”是否相同；合并时，我们关心的是两个集合能否重新划分。由于集合关系会随着合并不断变化，这也就是“动态连通性”的直观含义。

在形式化描述中，我们可以把“两个元素属于同一个集合”理解为一个等价关系。等价关系满足自反、对称、传递，而集合划分恰恰对应着一种等价关系。对并查集来说，判断两个元素是否等价，只需看它们找到的代表元是否相同。

回到村庄的例子：只要两个村民最终站到同一个祠堂前，不管他们中间隔了多少辈分，他们一定属于同一个家族；这就是并查集最基本的判断逻辑。

树形表示

家族的族谱不会把几万人画在一张平面图上，否则根本看不清。更自然的做法是让每个人只记一个“父亲”：父亲再记自己的父亲，一路往上，直到某个人的父亲栏写着自己，那个人就是老祖宗。整个村庄因此形成多棵“倒挂的树”，每棵树代表一个家族，树根就是家族代表元。

并查集也采用同样的树形表示。它用一个数组 parent 来存放每个节点的父节点：如果 parent[x] == x，说明 $x$ 是根；如果 parent[x] != x，说明 $x$ 的父亲是 parent[x]。多个这样的树放在一起，就叫森林。查询根节点时，只需要顺着父指针一路向上走。

在这种表示下，“一个元素属于哪个集合”变成了“它所在的树的根是谁”。根节点不仅代表一棵树，也代表整个集合的身份。任何两个元素只要根相同，就属于同一个集合。

“父指针指向自己”就是祠堂门前的族徽。只要看到这个标记，我们就知道已经追到了家族源头，这一趟寻亲之路可以结束了。

核心操作

并查集有三种基本操作：初始化、查找和合并。初始化时，每个元素都自成一个家族，所以 parent[i] = i。查找操作负责从某个节点出发，沿着父指针一路向上，找到树根。合并操作则先找两个元素的根，如果根不同，就把其中一棵树的根挂到另一棵树的根下面，两族从此成为一族。

查找操作通常写成 find(x)。如果当前节点的父亲不是自己，就继续找父亲的父亲，直到遇到根。这是一个跟随父指针不断向上的过程。合并操作 union(a, b) 则表达为：先得到 $a$ 的根和 $b$ 的根，如果二者不同，就让其中一个根成为另一个根的父节点。

我们可以把合并写成下面的形式。这里 $\operatorname{root}(a)$ 和 $\operatorname{root}(b)$ 分别代表 $a$、$b$ 所在树的根。

这里还没有引入优化，所以谁挂到谁下面都可以。但如果我们不小心让高树挂到矮树下面，族谱就有可能会变成一条很长的链，查询时就要走很远。这正是后面两种优化要解决的问题。

路径压缩

想象你为了确认自己的老祖宗，沿着族谱一级一级往上爬，爬了十代人终于到了祠堂。如果下次还要再爬一次，实在累人。聪明的做法是，回去之后立刻把沿途所有人的父亲栏都直接改成老祖宗。这样下次再有人问路，一步就能到达祠堂。

这个操作就是路径压缩。它发生在查找过程中：当 find(x) 找到了根之后，递归返回时会把路径上每个节点的父指针都直接指向根。于是整条路径被“压扁”，以后的查找代价大大降低。

路径压缩的实现非常简洁。如果当前节点不是根，就递归调用 find，并把结果赋给当前节点的父指针。这个赋值就是“把父亲栏改成老祖宗”的动作。

路径压缩让树变得更扁，但不会增加树的高度，反而只会降低高度。因此它和按秩合并可以同时使用，而且互不冲突。

按秩合并

如果两族联姻时，每次都让高大的祠堂挂到矮小的祠堂下面，过不了多久族谱就会歪成一根细长的藤蔓。更稳妥的做法是：让矮树挂到高树下面，这样整体高度不会增加；只有两棵树一样高时，才不得不增加一层，并把新根的“秩”加一。

这个“秩”就是树高的上界。在并查集中，我们给每个根维护一个 rank 值，近似表示这棵树有多高。合并时比较两个根的秩，秩小的根挂到秩大的根下面；如果秩相等，则任选一个根作新根，并让新根的秩加一。这保证了树的高度始终被控制在 $O(\log n)$ 级别。

假设 $r_a = \operatorname{root}(a)$，$r_b = \operatorname{root}(b)$，按秩合并的规则可以写成：

按秩合并保证了即使没有路径压缩，每次查找的最坏时间也只有 $O(\log n)$。路径压缩再把这个上界进一步压缩到几乎常数级别。

复杂度分析

有人会担心：路径压缩每次都会改动树的结构，按秩合并又需要维护秩，这些操作加起来会不会很慢？实际上，并查集的魅力正在于它的“均摊”效率极高。均摊的意思是：把一长串操作的总代价加起来平均，每次操作的成本低得惊人。

设共有 $n$ 个元素，连续执行 $m$ 次 find 和 union 操作，同时使用路径压缩与按秩合并，总时间复杂度为：

其中 $\alpha(n)$ 是反阿克曼函数。它的增长速度极其缓慢，以至于在宇宙原子数级别的 $n$ 下，$\alpha(n)$ 也不会超过 5。因此每次操作均摊下来几乎就是 $O(1)$，这也是并查集被称为“近乎常数级”数据结构的原因。

正因为均摊接近常数，并查集才敢被用于千万级甚至亿级节点的大规模图计算中。它把“动态连通性”这个听起来很重的问题，变成了几乎每个操作只需眨一下眼的轻活。

经典应用

家族族谱不仅能用来认亲，还能解决许多图论问题。第一个典型应用是连通分量判定：给定一张无向图和若干条边，判断两个顶点是否连通。我们只需把所有边依次做 union，最后查询两个顶点的根是否相同即可。这就像根据村庄道路，逐步把能互通的村子合并到同一个家族里。

第二个典型应用是 Kruskal 最小生成树算法。算法的思路是把所有边按权重从小到大排序，然后逐条尝试加入。如果一条边的两个端点已经连通，加入它就会形成环，必须跳过；如果没有连通，就加入这条边并把两个端点合并。这里 union 的返回值恰好能告诉我们“是否成功合并”，从而自然地避免成环。

判断一条边是否能加入最小生成树，可以写成：

第三个典型应用是等价类判定。比如在编译器中判断两个变量是否属于同一个“等价类”，或在社会网络中判断用户是否属于同一个群体。只要把“相等”“互粉”“同源”这些关系看成一条条待合并的边，并查集就能快速维护所有等价类。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-class UnionFind:    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, a, b):        ra = self.find(a)        rb = self.find(b)        if ra == rb:            return False        if self.rank[ra] < self.rank[rb]:            self.parent[ra] = rb        elif self.rank[ra] > self.rank[rb]:            self.parent[rb] = ra        else:            self.parent[rb] = ra            self.rank[ra] += 1        return True     def connected(self, a, b):        return self.find(a) == self.find(b)  def connected_components(n, edges):    uf = UnionFind(n)    for a, b in edges:        uf.union(a, b)    return len({uf.find(i) for i in range(n)})  def kruskal_mst(n, edges):    uf = UnionFind(n)    edges = sorted(edges, key=lambda e: e[2])    total = 0    for u, v, w in edges:        if uf.union(u, v):            total += w    return total  if __name__ == "__main__":    edges = [(0, 1), (1, 2), (3, 4)]    print("components:", connected_components(5, edges))    weighted = [(0, 1, 4), (1, 2, 2), (0, 2, 5), (2, 3, 3)]    print("mst weight:", kruskal_mst(4, weighted))

1. self.parent[x] = self.find(self.parent[x])路径压缩，查找时直接把当前节点挂到根上。
2. if self.rank[ra] < self.rank[rb]按秩合并，矮树挂到高树下面。
3. else: self.parent[rb] = ra; self.rank[ra] += 1两棵等秩树合并时，新根秩加一。
4. len({uf.find(i) for i in range(n)})统计有多少个根，就是多少个连通分量。
5. if uf.union(u, v):Kruskal 中合并成功则加入边，合并失败说明会成环。

常见误区

面试题