学习顺序主线第 20 / 22 课 · 阶段 6

为什么现在学:已经会遍历判断连通后,再学习多次查询如何避免重搜。

返回算法课程
图与搜索进阶

并查集Union Find

通过集合代表快速判断两个节点是否连通,并合并它们所在的集合。

40 分钟前置:数组 · 图的连通性

学完这一课,你应该能做到

  • 分清节点、父指针和集合代表
  • 只合并不同根,并维护分量数
  • 解释路径压缩为何不改变连通性

01先从一个问题出发

朋友圈不断合并时,快速回答两个人是否已经在同一个圈子。

一个具体的例子

4 个节点,依次加入 (0,1)、(2,3)、(1,2)、(0,3)。大小相同则保留本次第一个根。

只问属于哪一组,不必每次找路线

图不断加入边,反复询问两点是否连通。每次 BFS 都能回答,却会重复搜索。并查集给每个连通组选择一个代表根;两个节点沿父指针找到同一根,就属于同一组。它记录分组,不负责还原图中的实际路径。

初始 n 个节点各自成组,parent[i]=i,size[i]=1,分量数为 n。加入边 (a,b) 时先求 find(a)、find(b)。如果根相同,已经连通,分量数不变;不同才把两组接起来。

两种压低树高的办法

按大小合并时,把较小集合的根接到较大集合的根上。必须修改根的父指针,而不是随便把 b 接到 a;后者可能只移动某一子树,破坏整组关系。只有根的 size 被用来代表集合大小。

路径压缩让查询经过的节点更接近根。本课采用路径减半:沿途把 parent[x] 改成 parent[parent[x]],然后继续走。祖父和当前节点原本就在同一组,所以改捷径不会改变组成员。父指针不是原图边,不要求这条捷径在原图中真实存在。

02最直接的办法,为什么慢?

每次询问连通性,都重新进行 BFS。

暴力 · O(V+E) / 次

图不断加边、询问很多时,重复搜索整张图成本很高。

03一步步,推导出优化思路

1

用共同的根代表一个集合

每个集合选一个根作为代表,父指针连接到根。

2

查询时缩短父指针路径

find 走父指针,路径压缩把中途节点直接拉近根。

3

把小集合的根接到大集合

union 按大小把小树接到大树,减少未来查询深度。

贯穿算法的不变量

两个节点连通,当且仅当 find 得到相同的根。

拿一个小输入,逐步手算

4 个节点,依次加入 (0,1)、(2,3)、(1,2)、(0,3)。大小相同则保留本次第一个根。

边两端根parent[0..3]分量数
初始各自为根[0,1,2,3]4
(0,1)0 / 1[0,0,2,3]3
(2,3)2 / 3[0,0,2,2]2
(1,2)0 / 2[0,0,0,2]1
(0,3)0 / 0[0,0,0,0]仍为 1;find 缩短了 3 的路径

合并完成不要求每个节点立刻直接指向根。第三步 parent[3]=2 仍合法,因为沿 3→2→0 能找到同一个代表。

分组与图的连通性同步变化

  1. 初始没有边,每个节点单独连通,与独立集合一致。
  2. 加入连接两个不同分量的边时,把两个根连接,恰好合并这两个集合;组内加边不改变集合划分。
  3. 路径压缩只把父指针改到同一条祖先链上,不改变最终根。按边加入顺序归纳,集合划分始终等于当前无向图的连通分量。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Union Find交互演示
STEP 01 / 10
0123
无向图 · 源点 0 · 邻居按编号处理
当前处理已处理 / 已确定未处理
01

每个节点最初独立成为一个集合。按图中边的输入顺序合并。

union_find.py参考实现 · 当前第 2 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

while parent[node] != node:
根的定义是父指针指向自己;不是编号最小,也不是原图中度数最大的点。
parent[node] = parent[parent[node]]
本次让节点跳向祖父,属于路径减半,不是一次就把整条链的所有节点都改为根。
if root_a == root_b:
相同根直接跳过,不要再次减小分量数,也不要重复把 size 相加。
parent[root_b] = root_a
在必要的大小比较和交换后,连接两个根;随后更新胜出根的 size,count 减一。

05复杂度,来自具体的工作量

时间复杂度
O((V+E)α(V))O((V+E)\alpha(V))

初始化 O(V),每条边调用 find 并至多一次合并。路径压缩 + 按大小合并的单次操作摊还为 O(α(V)),α 是增长极慢的反阿克曼函数。

辅助空间
O(V)O(V)

parent 和 size 数组各有 V 项。

拖动 n,看看增长速度

把工作量具体数出来

初始化 parent、size 花 O(V)。路径压缩配合按大小合并,长期操作序列中的每次操作摊还 O(α(V)),α 增长极慢,但并不是数学上严格的常数。

处理 E 条边,较精细地写为 O(V+E·α(V));宽松上界也可写 O((V+E)α(V))。不要把摊还保证说成每一次 find 都只走一步。

parent 与 size 各保存 V 项,辅助空间 O(V)。基本并查集支持不断合并,不直接支持删边后的分裂。

06看到什么,应该想到它?

这些特征值得停下来想一想:

关键词只是线索,继续检查适用条件

07这些细节,容易踩坑

01

合并的是根

不要直接连接任意节点,否则可能破坏集合关系。

02

不适合直接删边

基本并查集只适合合并;删边需离线技巧或更复杂结构。

用反例检查前提

组内加边不能再次减少组数

0–1、1–2 已让三点连通,再加入 0–2,只多出一条环上的边,连通分量仍为 1。若每条边都 count--,最终会错误得到 0。

怎样修正:只在两个根不同、确实合并了两组时减一。同一规则也可用来识别无向图中加入哪条边会形成环。

08把想法带进真实题目

合上答案,自己推一次

自己维护分量计数

5 个独立节点,依次加入 (0,1)、(1,2)、(0,2)、(3,4)。每步分量数是多少?最后 2 与 4 是否连通?

需要一点提示

第三条边的两端已经有相同根。

查看完整推导与答案
  1. 初始 5 组,前两条边后分别为 4、3。
  2. 加入 (0,2) 不改变分组,仍为 3;加入 (3,4) 后变成 2。
  3. 最终两组为 {0,1,2} 和 {3,4},2 与 4 不连通。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01如何判断两个节点连通?

02路径压缩改变连通性吗?

03同集合内再加一条边,分量数怎么变?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。