并查集路径压缩与按秩合并：从原理到面试实战

前几天一个准备跳槽的朋友找我复盘面试说某头部互联网公司的面试官问了一道看着特别基础的数据结构题并查集的路径压缩和按秩合并。他本来觉得这是个送分题结果对方从“为什么要做路径压缩”问到“两个优化能不能只用一个”从递归写法问到迭代写法最后还追了一句“你知道这两个优化合起来的均摊复杂度是多少吗”。我听完忍不住笑了这道题确实是面试里的经典试金石。并查集Union-Find是算法面试里出现频率极高的数据结构几乎所有和“连通性”有关的题目都会用到它判断两个节点是否在同一个集合、合并两个集合、统计连通分量数量、检测图中是否存在环。而路径压缩和按秩合并这两个优化直接决定了并查集从“能用”变成“能用得飞快”也是面试官考察候选人是否真正理解底层原理的分水岭。这篇文章我会把并查集从基础实现到双优化完整讲透顺便把面试中可能出现的追问和易错点全部梳理一遍无论你是准备校招还是社招刷题这都可以作为一份比较完整的复习笔记。1. 先把问题定义搞清楚并查集到底在解决什么1.1 动态连通性问题很多资料一上来就扔代码反而把最核心的问题定义忽略了。并查集解决的是一个名叫“动态连通性”Dynamic Connectivity的问题给定 n 个元素初始时每个元素各自独立然后不断执行两类操作——把两个元素所在的集合合并union或者查询两个元素是否在同一个集合中connected/find。合并操作是“动态”的因为集合的归属关系会随着操作不断变化。你可以把它想象成一场持续进行的交友派对每个人一开始都是独立的个体每执行一次 union就等于给两个人牵了条线让他们所在的社交圈合并每执行一次 find就是在问“这两个人现在是不是一个圈子里的”。圈子之间还会不断合并关系网越来越复杂但并查集通过巧妙的树形结构始终能在很低的时间里回答这些“是不是一个圈子”的问题。这种问题在现实中的对应场景非常多社交网络里两个用户是否属于同一好友链、计算机网络中两个节点之间的链路是否连通、图像处理里判断哪些像素构成同一个连通区域。也正因如此并查集在面试题里几乎是“必考数据结构”之一。1.2 核心操作与最朴素的数组实现并查集最经典的实现方式是使用一个数组 parent记录每个元素的“父亲节点”。设计很简单如果 parent[i] i说明 i 是自己的根也就是这个集合的代表元如果 parent[i] j说明 i 的父亲是 j。判断两个元素是否属于同一集合就去顺着这条父子链找到各自的根看根是否相同。基础版的 Java 代码长这样class UnionFind { private int[] parent; public UnionFind(int n) { parent new int[n]; for (int i 0; i n; i) { parent[i] i; } } // 找到 x 所在集合的根节点 public int find(int x) { while (parent[x] ! x) { x parent[x]; } return x; } // 合并 x 和 y 所在的集合 public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; } } // 查询两个元素是否连通 public boolean isConnected(int x, int y) { return find(x) find(y); } }find 就是沿着父亲指针一直往上走直到根union 则先分别找到两个元素的根再让其中一个根指向另一个根。至于为什么不直接把 parent[x] y而是先找根再改根原因很简单如果直接把 x 挂在 y 下面那 parent[x] 不再指向原来的集合原来 x 所在的整个集合就和 y 的集合断开了关联非常容易出错。所以 union 的正确姿势一定是“根连根”。1.3 基础版的性能瓶颈在哪里基础版能跑但性能完全没法看。假设有 n 个元素最坏情况下按顺序不断合并比如先合并 0 和 1再合并 1 和 2再合并 2 和 3……每次 union 都把前一个根挂到新元素下面最终会形成一条长度为 n 的链。此时 find 查找末尾元素的根需要一路爬过 n 个节点单次查找的复杂度是 O(n)整个并查集就退化成了一个慢速链表。这种退化不是理论上的极端案例而是很容易触发的常见场景。比如一次循环里连续执行 n 次 union如果你总是固定把 rootX 指向 rootY贪吃蛇式的长链就产生了。后面要讲的按秩合并就是专门用来防止这种“退化成长链”的情况发生而路径压缩则是让即使偶尔出现的深树也能在查找过程中被快速压扁。2. 路径压缩让每一次查找顺便把树压扁2.1 核心思想沿途把节点直接挂到根上路径压缩Path Compression的思路很朴素既然 find 的时候反正要沿着路径走到根不如在走的过程中把经过的每个节点全部直接连到根上去。这样一次 find 下来这条路径上的所有节点都不再经过中间层下一次再查这些节点时一步就能到达根几乎瞬间完成。你可以这样理解想象你是一个办事员每次要沿着一条长长的走廊走到底找领导签字走廊中间有许多同事。正常操作是你一路敲门一路走签完字再原路返回。路径压缩的做法是你走出这一趟的同时给每个同事递了一句话“这位领导的办公室在这头你们以后直接来找他就行。”于是下次这些同事办事都不用再走完整条走廊了。这个优化最大的特点是它没有额外的时间开销find 过程中顺带完成不增加整体操作次数只是多做了几次赋值操作。但它带来的收益是巨大的因为一旦路径被压缩后续所有针对这些节点的 find 都变成 O(1) 级别的操作。2.2 递归版本和迭代版本的差异路径压缩最经典的写法是递归版public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; }这段代码逻辑非常清晰如果 x 不是根就让 x 的父节点递归执行 find然后把 x 直接挂到返回的根上。等号左边 parent[x] 右边的根这就是在“压路径”。递归代码看起来优雅但有一个隐患当树很深时递归深度可能很大极端情况下能触发栈溢出StackOverflowError。虽然在实际题目中树深度一般不会大到栈溢出但如果你在做超大规模数据或者对安全性要求很高的系统还是建议用迭代版本。迭代版本分两步走先找根再二次遍历压路径public int find(int x) { // 第一步找到根节点 int root x; while (parent[root] ! root) { root parent[root]; } // 第二步把路径上所有节点的父节点直接改成根 while (parent[x] ! x) { int next parent[x]; parent[x] root; x next; } return root; }这个迭代版本虽然代码量多一点但完全避免递归栈空间的消耗在临界情况下更稳。我在做大规模并查集题目时基本都用迭代版一方面不用担心 StackOverflow另一方面笔试环境里递归也容易踩到默认栈大小的坑。2.3 为什么路径压缩能显著提升性能路径压缩的本质是在“分摊成本”某一次 find 可能确实要消耗 O(n) 的时间去走完一条长路径但走完之后这条路径上的所有节点都变成根的直接子节点后续再对它们做 find代价就是一步。也就是说这次漫长的查找为后续大量的查找“预付”了成本。所以从整体均摊的角度看即使不做按秩合并单独使用路径压缩连续 m 次操作的总代价也能摊到非常小严格的理论分析会到达对数级别左右。面试时如果被问“只做路径压缩行不行”你可以回答可以性能也比裸并查集好很多但依然建议配合按秩合并因为单独路径压缩在某些特定操作序列下仍可能出现单次 find 代价较高的波动两者结合起来才能获得稳定且接近常数的均摊复杂度。3. 按秩合并从源头上阻止树长高3.1 为什么要控制树的高度路径压缩是“事后补救”——树已经长歪了靠 find 的时候顺便压扁这种方式很好但它有一个弱点如果你一直只做 union 不执行 find树照样会越长越高长成一条细长的直线那等真正需要 find 时可能已经是 O(n) 的深度了。这时候就需要第二个优化按秩合并Union by Rank它的思路是在 union 的时候通过选择“让哪棵树的根挂到另一棵树的根下面”主动控制树的高度增长。本质上就是一句话永远把较矮的树挂到较高的树上。这个思路在生活中也很常见公司合并的时候通常会把小团队并入大团队而不是反过来把大团队挂到小团队下面否则整个组织会变得头重脚轻汇报链越来越长。3.2 rank 的本质树高的上界估计按秩合并里引入一个数组 rank表示这棵树“大致有多高”。初始时每个孤立节点的 rank 都是 0。union 的时候比较两个根节点的 rankrank[rootX] rank[rootY]让 rootX 指向 rootY树高不变。rank[rootX] rank[rootY]让 rootY 指向 rootX树高也不变。rank[rootX] rank[rootY]选择任意一个作为新的根比如让 rootY 指向 rootX同时把新根的 rank 加 1。为什么只有 rank 相等时才需要加 1因为两棵高度相同的树合并无论谁挂谁得到的新树高度一定比原来高一层而两棵高度不同的树合并把矮的挂到高的下面总高度就是高者的高度不会增加。这个逻辑保证了整个并查集的树高在没有任何路径压缩的情况下也不会超过 log(n)这里的 log 表示以 2 为底的对数。为什么高度一定不超过 log(n)可以这样想只有 rank 相等的两棵树合并树高才增加 1而每棵 rank 为 k 的树至少包含 2^k 个节点。也就是说高为 k 的树至少要由 2^k 个节点构成那么 n 个节点组成的树高最多就是 log(n)。这个结论本身就是面试中一个很好的加分考点很多人知道按秩合并但说不清楚为什么它能保证对数高度。Java 版按秩合并的 union 代码如下private int[] rank; public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } }这里需要特别提醒一个细节rank 并不等于“路径压缩之后的真实高度”。因为路径压缩会改变树的形态让树高变矮但我们不会再去动态更新每棵树的 rank。这其实是刻意为之因为 rank 在路径压缩存在时它的角色从“精确高度”变成了“树高的上界估计”。就算真实高度变小了用这个上界去指导合并方向依然不会破坏算法的正确性和复杂度上界同时又避免了维护真实高度的巨大开销。3.3 按秩合并 vs 按大小合并到底选哪个还有一个常被问到的变体不一定使用 rank树高也可以使用 size集合中元素数量称为“按大小合并”Union by Size。两种做法的核心逻辑都是“让大树并小树不让小树并大树”但细节略有差别策略合并依据优点典型写法按秩合并Union by Rank树高估计理论高度更可控证明更干净rank 数组按大小合并Union by Size集合元素数量直观且在某些围绕子树大小统计的场景更实用size 数组在实际刷题中两者都能让并查集达到接近常数的均摊复杂度。我个人在回答面试问题时优先提“按秩合并”因为面试官更常听到这个词且它和“限制树高”的语义直接挂钩。但在写代码时如果你觉得 size 版更好记、更不容易写错也没有问题关键是讲清楚你选择背后的理由不要只会背模板。4. 两个优化合体完整代码模板与复杂度真相4.1 面试手撕用的完整 Java 模板把路径压缩和按秩合并都加上并查集的完整代码模板如下class UnionFind { private int[] parent; private int[] rank; private int count; // 当前连通分量数量 public UnionFind(int n) { parent new int[n]; rank new int[n]; count n; for (int i 0; i n; i) { parent[i] i; } } public int find(int x) { // 非递归路径压缩 int root x; while (parent[root] ! root) { root parent[root]; } while (parent[x] ! x) { int next parent[x]; parent[x] root; x next; } return root; } public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; } public boolean isConnected(int x, int y) { return find(x) find(y); } public int getCount() { return count; } }这里加了一个 count 字段没什么魔法就是每次合并成功后连通分量数减一。别小看这个字段刷“岛屿数量”“省份数量”这类题时求结果就是一句 getCount() 的事非常顺手。4.2 均摊复杂度反阿克曼函数到底是什么两个优化全部用上之后并查集执行 m 次操作的总均摊时间复杂度是 O(m · α(n))其中 α(n) 是反阿克曼函数Inverse Ackermann Function。这个函数增长极其缓慢——慢到什么程度呢对于宇宙中所有原子数量级别的 n大约 10^80α(n) 也不会超过 5。换句话说在实际应用中并查集的 find 和 union 完全可以当作 O(1) 来看待。面试官可能会好奇追问 α(n) 为什么这么小。你可以打个比方阿克曼函数是那种指数爆炸级别的函数它的增长速度远超我们见过的任何指数函数而反阿克曼函数就是阿克曼函数的逆也就是说要让 α(n) 超过 4n 必须大到是一个根本无法用物理世界数量描述的巨型数字。因此“常数级别”这个说法在工程意义上是站得住的。但要说得严谨一些这个 O(m · α(n)) 是“均摊复杂度”不是单次操作的最坏复杂度。就是说单独某一次操作可能比 O(1) 慢一些但把连续的一串操作放在一起平均下来每个操作的耗时就是反阿克曼级别。这背后有一整套摊还分析Amortized Analysis的证明面试中不要求你完整复现但能说出“均摊”“几乎常数”这两个关键词基本上就过关了。4.3 面试高频追问两个优化能不能只用其中一个这个问题几乎是必问答案是“可以但都不如两个一起用”。单独按秩合并保证单次 find 的最坏复杂度是 O(log n)稳定但不够极致。树不会被压扁每次查找可能都要走 log n 层。单独路径压缩整体均摊表现很不错但存在弱点是如果操作序列中大量是 union 而很少有 find长链虽然会在某次 find 时被压扁但那次 find 之前树已经很高了某些时刻的单次操作代价依然可能很糟糕。从理论上看单独路径压缩的均摊复杂度也可以做到对数级别但不如两者结合后的反阿克曼级别。用一句话总结给面试官按秩合并是对 union 的优化从源头限制树高路径压缩是对 find 的优化在查询时削减树高。一个防患于未然一个事后补救两者不是重复的优化而是互补的。5. 面试实战从手撕代码到边界情况5.1 面试官最爱追问的 Top 8 问题我把常见的追问统一整理一下你可以作为自测清单为什么 union 要“根连根”不直接 parent[x] y路径压缩的递归实现有什么缺点如何改成迭代版rank 在路径压缩之后还是树的真实高度吗为什么可以不更新一味合并会导致原本的“矮树”挂到“高树”上吗rank 的大小到底能不能反映真实高度两个优化都使用后单次 find 的最坏复杂度是多少均摊复杂度又是多少如果给你 n 个点和 m 条边如何用并查集判断图里有没有环如何统计连通块的数量并查集的 count 字段什么时候减一并查集如何处理“元素编号不是从 0 开始的”情况比如省份名称、字符串节点。第 8 问其实很关键。笔试里经常出现元素不是连续整数的情况做法是引入一个 HashMap 做离散化映射把非连续元素映射到连续的数组下标再用并查集。比如 LeetCode 的除法求值问题就是典型的“字符串节点 并查集 权重”场景复杂度一下就上来了。这个扩展值得多聊一句带权并查集Weighted Union-Find在面试里也是进阶考察点但基础还是路径压缩和按秩合并地基不稳谈不了上层。5.2 笔试刷题里的易错点实录我自己刷题的时候踩过不少坑整理几个最容易翻车的点第一个坑初始化时把 parent[i] 写成 0。这个错误很隐蔽只初始化 parent 数组但忘记让 parent[i] i会导致每个节点都指向 0find 永远返回 0所有元素都“被连通”了结果全是错的。我第一次写时也栽在这里尺子要放准。第二个坑union 里先查 find 但不判断 rootX rootY 就直接合并。如果两个元素已经在同一个集合里还是不判断直接挂虽然 parent 指针不会坏但会导致不必要的操作更严重的是会让 count 错误地减一最终连通块数量就不对了。第三个坑rank 初始化为 1 还是 0。两种写法其实都行但如果用 rank 表示树高上界初始为 0 更合理用 size 合并时初始为 1 更合理。关键是整段代码风格统一不要混着来。第四个坑find 的递归版本在大数据量下栈溢出。排查时看到 StackOverflowError先想想是不是并查集的 find 写成了深递归。第五个坑在循环里反复 new 一个并查集导致初始化开销被忽略。如果数据量大初始化一次并查集是会循环 O(n) 的嵌套在循环里会导致整体复杂度上升一档。这里补充一个笔试中的提速小技巧很多算法题的并查集可以用数组模拟避免频繁的 Java 对象创建。比如一个长度为 n 的并查集直接开两个 int 数组代码反而更紧凑。所以我通常写一个内部类或者直接用局部方法减少对象封装带来的开销和代码噪音。5.3 并查集适合套用的经典题目模型面试和笔试里并查集题目基本逃不出下面几个模型连通分量数量给一个二维矩阵1 代表陆地0 代表海水统计有多少个岛屿。做法是遍历每个陆地和上下左右的陆地合并最后统计 count。这里有个细节一开始可以把每个陆地的 count 先做成 1然后每合并一次减 1也可以初始化为所有格子数再把海水的 count 扣掉更推荐前者不容易算错。冗余连接给一棵多了一条边的树需要找出哪条边可以删除让图重新变成树。用并查集遍历边在合并时发现两个端点已经连通说明这条边导致成环直接返回。最长连续序列给一个乱序数组找出最长连续数字的长度。用并查集合并相邻的数字或者在去重后用哈希表做“连续扩展”两种思路都能做并查集版本适合练手。动态连通性在线查询在线处理多组 union 和 isConnected 操作适合作为模板题打底。这些题目的共同点就是核心思路是维护“集合关系”难点往往是两步第一步想清楚节点是什么第二步想清楚“什么情况下两个节点要 union”。一旦这两点清晰代码几乎都是模板差异只在数据结构和边界处理上。6. 从面试题到实际工程并查集在真实场景中的落点6.1 社交网络中的好友关系很多社交产品中用户关系的“连通块”是一个常见需求A 是 B 的好友B 是 C 的好友那么 A 和 C 虽然没有直接好友关系但处于同一个社交链中。如果你想实现“两个人是不是在同一个好友圈子”这种查询并查集是最直接的数据结构每次添加好友关系就 union 一次每次验证就 find 一次。它的优势在于几乎不需要额外的维护成本不需要 BFS/DFS 从一个人出发去遍历整个图。虽然严格来说好友关系是“双向的”但在很多只需要“是否连通”的轻量场景里并查集就能快速给出答案。实际生产里如果数据量非常大会把并查集封装成一个带持久化的服务定期把数组状态快照落到存储中保证重启后能恢复连通关系。6.2 网络拓扑与分布式系统计算机网络里判断两台交换机是否处于同一连通域、一组节点之间是否形成环这类问题也可以用到并查集。路由环路检测、集群里节点分组管理本质上都是“动态连通性”的应用。举个例子假设有 n 台服务器不断有新的物理链路建立同时需要快速判断某两台服务器是否已经互通。每建立一条链路就执行一次 union每次查询就执行一次 find一次链路建立和查询的耗时都在微秒级。如果换成 BFS/DFS每建立一条链路重新扫描整个图代价就要高出几个数量级。在高频变化场景下这个差距非常明显。6.3 最小生成树的 Kruskal 算法业界最著名的并查集应用当属最小生成树算法 Kruskal把图的所有边按权重从小到大排序依次考察每条边若边的两个端点还没有连通就把它们合并并把这条例外纳入最小生成树若已经连通说明这条边会和已有的边形成环跳过。全部边遍历完后得到的就是最小生成树。Kruskal 的正确性依赖一个关键前提需要快速判断“两个端点是否连通”这正是并查集的主场。没有并查集的 Kruskal 会慢到没法用因为每次判断连通性如果都做一次全图遍历整个算法就成了 O(E·V) 级别的灾难而用了带两个优化的并查集Kruskal 的主体复杂度就变成排序的 O(E log E)并查集部分几乎可以忽略不计。这个例子也很好地解释了为什么面试官会在考 Kruskal 之前先考并查集——Kruskal 几乎就是并查集的实战题。我在实际面试中会建议候选人这样组织回答先讲清楚模型再讲优化最后落到复杂度。比如面试官问“为什么 Kruskal 需要用并查集”不要只说“为了判断是否成环”而是把“成环判断”的语义翻译成“两个节点的连通性查询”然后自然引出 find 和 union以及为什么这里的查询特别频繁、必须用接近常数的数据结构。这种回答逻辑比单纯背结论要让人信服得多。7. 一些踩过坑之后的个人经验最后分享几条我个人刷题和面试积累下来的心得。第一并查集模板不要只背一种写法至少把递归 find 和迭代 find 都写熟练因为面试官很可能让你当场写第二种写法。第二笔试时如果时间紧张优先跑通功能再考虑优化但面试中恰恰相反面试官更看重你在写代码前能不能把复杂度分析和优化取舍说清楚。第三花一点时间把带权并查集路径上额外维护权重信息的题目做几道很多算法面试的终面题都会从这里出等你把基础的路径压缩和按秩合并彻底吃透了再往带权版本延伸会顺手很多。并查集这只“纸老虎”其实不难难的是真正理解它每一步设计背后的代价和收益。下一次面试再被问到“并查集的路径压缩和按秩合并”希望你能从容地从问题定义讲起一路讲到反阿克曼函数把面试官想问的细节全部覆盖到位。