简述
并查集(Union Find)是图论中的高级算法,常用来解决连通性问题, 不过因为并查集算法本身的实现是基于树结构的,所以有不少人把并查集算法归类在树的下面。Leetcode上需要用并查集解的题目没有"简单"的,大多数单纯使用并查集的题目难度都是属于"普通"偏难的,而如果题目在使用并查集的基础上随便加点什么陷阱或限制,基本是典型的"困难"题。
不开玩笑的说, 很多已经找到工作的开发者也未必系统了解过并查集, 因为并查集学习难度比较大,再加上图论的问题本身在coding test中不占特别大的比重(这个比重正比于图论的使用在公司业务中的占比),而且图论值得考察的题型又特别多,DFS/BFS和Dijkstra出现的概率远比并查集高得多,所以因为不会并查集而挂掉面试其实属于小概率事件,因此也有人就认为并查集没必要钻研 (当准备时间有限的时候确实需要作出这样的取舍)。
不过好在,类似并查集这种高级算法的一大特点就是他们能够解决的问题通常比较specific,因此在遇到连通性问题的时候也很容易想到要用并查集。再加上并查集的实现也相对有套路,最坏的情况下套用代码模板也基本上可以解决"普通"难度的并查集问题。
总结一下, 并查集需要关注两个点:
- 并查集能解决什么问题(什么时候该用并查集)
- 并查集怎么实现(为什么并查集可以做到,而别的算法不行)
并查集的难点⭐️
学习并查集的时候有两个非常大的误区,要尽可能避免:
- 硬钢概念: 有的算法初学者喜欢脱离问题,直接去看一些算法的概念,对于一些简单的算法这么做无可厚非,但是对于高阶算法,这种学习方式应该尽可能避免。因为并查集本身的实现相对于其他的高阶算法也是偏复杂的,直接看代码模板和背后的原理很容易被难度劝退。
- 硬套模板: 这个其实是在有通用模板的算法笔记下会反复强调的,毕竟模板是基于算法设计的,而不是基于问题设计的,我不否认遇到类似的问题使用模板效率很高,但是如果问题稍微套一层壳子,那么硬套模板一定会陷入非常狼狈的境地。
并查集基本概念
前面简单提了一下,并查集解决的是连通性的问题。直白点讲,就是 当我们需要判断两个元素是否在同一个集合里的时候,我们就要想到用并查集。
而想要判断两个元素是否在同一个集合,算法最起码需要能够做到两点:
- 将两个元素添加到一个集合中。
- 判断两个元素在不在同一个集合。
这两点乍一听有种把人当智障一般的简单,但其实想要做到这两点其实并不容易。
并查集的实现⭐️
代码实现的秘诀:「表示"连通"的数据结构」
从代码层面,我们如何将两个元素添加到同一个集合中呢?最直观的方案可能是: 创建一个数组里或者set 或者 map,当两个元素被放置到同一个set/map/array时,就表述两个元素在同一个集合。
逻辑上这个方案其实是最符合实际的,但是在算法领域中我们不得不考虑的问题是: 对这些元素分门别类,可不止一个集合,可能是成百上千个集合,那么要定义这么多个数组吗？
但是可以退一步,上述问题,其实可以使用二维数组来解决, 可以实现对大量集合的管理,但是还是治标不治本,因为目前为止我们还只是解决了第一点「将两个元素添加到一个集合中」,如果使用二维数组解决第二点「判断两个元素在不在同一个集合」,会发现除了遍历完整个二维数组外没有任何捷径。更重要的是,每一次添加元素到某一集合也需要把二维数组都遍历一遍,才知道要放在哪个集合里。
如果将思维固化在使用数组或者哈希表,那么代码的实现一定会非常复杂,因为管理集合需要大量的逻辑去控制,因此我们显然需要换一个思路: 一个从连通性角度出发的思路。
如果我想要表示三个元素,记为 A, B, C,三者是连通的, 只需要一个简单的哈希表,甚至一维数组就可以实现, 只要能够表达出 father[A] = B, father[B] = C的关系就行。
熟悉图论的其实都能理解,这就是有向连通图
其实很多算法学习者在思考的过程中应该也考虑过这种表达,但是可能后来自我否决了。因为想要继续深入思考的一个思辨难关就是: father[A] = B可以表示从A可以联通B, 如何表示B也连通A?
会卡在这个问题无可厚非, 因为开发的过程中难免要思考: "当在遍历题目入参数组时, 如果先遍历到B, 岂不是无法从B确定跟A的连通性?"
这个问题的答案是: 不能表示, 也不用表示。
因为我们的目的是判断三个元素是不是存在于一个集合, 所以只需要确定单向的连通性足矣。道理也很简单: 那就是溯源, 既然光从B出发无法确定跟A的连通性, 那索性规定大家都一起往同一个方向走到底。
我们不难发现通过father[A] = B, father[B] = C有向连通图, 给出B, 可以知道B与C联通, 给出A可以知道, A与B连通, 而B又与C连通, 因此,我们可以称C为 A和B共同的"根", 所以我们可以大胆去构建有向连通图, 只要能够确定任何两个元素具有相同的连通根时,就一定可以确定两者在同一个集合,反之亦然。
思考至此,代码实现也初见眉目,这种层层嵌套的溯源非常适合用递归来写,该部分代码模板如下。
father = dict()
... # 有向连通图的构建过程略
def find(u: int) -> int:
if (u == father[u]): # 如果根就是自己, 直接返回
return u
return find(father[u]) # 如果根不是自己, 继续一层层找根
代码中使用的是一维数组实现有向连通图,为了更优雅地设置递归的终止条件,选择让根元素指向自己,所以在实际上的初始化中,别忘了father[i]=i,默认自己指向自己,之后再根据连通情况更新。初始化部分代码如下。
arr = [...] # 入参的连通数组
def init():
for i in range(max(arr)):
father[i] = i
当然了,如果使用哈希表的话,就可以通过判断father[u]是否为空来判断是否为根。
在这个基础上,想要判断两个元素是否在同一个集合内就简单了,代码如下。
def is_same(u: int, v: int) -> bool:
u = find(u)
v = find(v)
return u == v
至此, 我们已经正式实现了第二点「判断两个元素在不在同一个集合」。至于第一点「将两个元素添加到一个集合中」,除了无脑构建有向连通图,其实还有更聪明的办法。
优化:「路径压缩」
之前的做法是通过递归的方式去实现find函数,不断获取father数组下标对应的数值,直到找到根。但是递归深度是一个决定性能的问题,如果有向连通图的深度很深,那么每次find函数都要递归很多次去寻找根,重复之下会拉高性能, 如图。
我们的目标只需要知道这些节点在同一个根下就行,所以完全可以通过把所有节点全部直接挂载在根节点下的方式来控制这个递归树的深度。如图:
这样我们在寻根的时候就很快,只需要一步。而我们想达到这样的效果,就需要 「路径压缩」,将非根节点的所有节点直接指向根节点。
具体的实现方式其实也不复杂, 只需要在递归的过程中让最终获取到的根节点信息不断往回传,并且重新赋予给father[u]就行。代码如下:
def find(u: int)->int:
if (u == father[u]):
return u
return father[u] = find(father[u]) # 这一步就是路径压缩的精髓
至此, 并查集的基础实现和原理就已经清楚了,整体代码模板见下。
并查集代码模板
n = 1005; # n根据题目中节点数量而定,一般比节点数量大一点就好
father = [i for i in n] # 并查集初始化
# 并查集里寻根的过程
def find(u: int) -> int:
if u == father[u]:
return u
return father[u] = find(father[u]) # 路径压缩
# 判断 u 和 v是否找到同一个根
def is_same(u: int, v: int) -> bool:
u = find(u)
v = find(v)
return u == v
# 将v->u 这条边加入并查集
def join(u: int, v: int):
u = find(u) # 寻找u的根
v = find(v) # 寻找v的根
if (u == v): # 如果发现根相同,则说明在一个集合,不用两个节点相连直接返回
return
father[v] = u
通过模板,我们可以知道,并查集主要有三个功能。
- 寻找根节点,函数:find(int u),也就是判断这个节点的祖先节点是哪个
- 将两个节点接入到同一个集合,函数:join(int u, int v),将两个节点连在同一个根节点上
- 判断两个节点是否在同一个集合,函数:isSame(int u, int v),就是判断两个节点是不是同一个根节点
开发误区:「等效替代」
并查集算法的实现中有一个很恶毒的陷阱,很容易翻车。因为很多不完全熟悉并查集原理的开发者都会注意到,在join函数和is_same函数中有一部分是重合的:
# 原始版
def is_same(u, v):
u = find(u)
v = find(v)
return u == v
def join(u, v):
u = find(u) # 重复
v = find(v) # 重复
if (u == v): # 重复
return
father[v] = u
于是,秉承复用的开发原则,很多开发者会做出如下优化
# "优化"版
def join(u, v):
if is_same(u, v):
return
father[v] = u
如果正在阅读的你认为这个优化没有问题,则请好好反思一下是否完全理解上文中的并查集原理。
错误的根源并不是在重复的部分, 而是在father[v] = u这部分。如果代入一些例子, 你就会发现在"优化"版的join函数中, 执行到father[v] = u这一行时, 和原始版执行到father[v] = u这一行时, u和v的值是可能不一样的。
e.g. 按顺序执行join(1,2), join(2,3)
原始版
join(1, 2)
father[2] = 1 (u = 1, v = 2)
join(2, 3)
father[3] = 1 (u = father[2] = 1, v = 3)
"优化"版
join(1, 2)
father[2] = 1 (u = 1, v = 2)
join(2, 3)
father[3] = 2 (u = 2, v = 3)
可以发现,"优化"版最大的问题就是: 跑完join(1,2)和join(2,3)之后, 执行is_same(1, 3)会return false, 因此完全违背了连通性的初衷。因此, 这个优化不应该被采纳。
图示:「并查集工作流程」
在该图示中, 依此执行如下操作:
- join(1, 8)
- join(3, 8)
- join(1, 7)
- join(8, 5) 发生「路径压缩」, 3取代1成为8新的根
- join(2, 9)
- join(6, 9)
优化:「按秩合并」
针对于并查集的优化方式, 除了「路径压缩」之外, 还有「按秩合并」。最开始我学习并查集的时候, 是直接看得概念, 看到按秩合并的时候给我劝退了。因为秩「rank」本身是一个很陌生的概念, 秉承着字越少事儿越大的心理, 想必秩也是个很难的概念。
但是事实上, 秩其实指的就是树的高度, 即有向连通图中从根到最远节点的距离。
按秩合并啥意思? 说白了就是当某一条边连通时, 需要将两个集合(递归树)合并时, A并入B 和 B并入A存在性能上的差异。
假设A的rank为2, B的rank为3。 若A并入B, 最终的连通图的rank是3。 而B并入A, 最终连通图的rank是4。 合并过程如图所示。
因此我们可以得出结论: 一定是rank小的树并入rank大的树, 从而降低整体树的rank, 以降低在树上查询的路径长度。
不过说句题外话。其实我们在优化并查集查询效率的时候，只用「路径压缩」的思路就够了，不仅代码实现精简，而且效率足够高。
按秩合并的思路并没有将树形结构尽可能的扁平化，所以在整理效率上是没有路径压缩高的。
并查集基础问题经典合集
| 编号 | 名称 | 难度 |
|---|---|---|
| 684 | 冗余连接 | 中等 |
| 685 | 冗余连接II | 困难 |
| 128 | 最长连续序列 | 中等 |
| 200 | 岛屿数量 | 中等 |
| 305 | 岛屿数量II | 困难 |
| 765 | 情侣牵手 | 困难 |
| 547 | 省份数量 | 中等 |
| 803 | 打砖块 | 困难 |