并查集

在计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个用于此数据结构的操作:

  • Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union:将两个子集合并成同一个集合。

由于支持这两种操作,一个不相交集也常被称为联合-查找数据结构(union-find data structure)或合并-查找集合(merge-find set)。其他的重要方法,MakeSet,用于建立单元素集合。有了这些方法,许多经典的划分问题可以被解决。

并查集

并查集是什么

并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以进行合并操作,但是却无法进行分割操作。

  • 查询元素 a 和元素 b 是否属于同一组。
  • 合并元素 a 和元素 b 所在的组。

uf-func

并查集的结构

并查集也是树形结构实现的。不过,不是二叉树。

uf-struct

每个元素对应一个节点,每个组对应一棵树。在并查集中,哪个节点是哪个节点的父亲以及树的形状等信息无需多加关注,整体组成一个树形结构才是重要的。

(1)初始化

我们准备 n 个节点来表示 n 个元素。最开始时没有边。

uf-initial-state

(2)合并

像下图一样,从一个组的根向另一个组的根连边,这样两棵树就变成了一棵树,也就把两个组合并为一个组了。

uf-union

(3)查询

为了查询两个节点是否属于同一组,我们需要沿着树向上走,来查询包含这个元素的树的根是谁。如果两个节点走到了同一个根,那么就可以知道它们属于同一组。

在下图中,元素 2 和元素 5 都走到了元素 1,因此它们属于同一组。另一方面,由于元素 7 走到的是元素 6,因此同元素 2 或元素 5 属于不同组。

uf-find

并查集实现中的注意点

在树形数据结构里,如果发生了退化的情况,那么复杂度就会变得很高。因此,有必要想办法避免退化的发生。在并查集中,只需按照如下方法就可以避免退化。

  • 对于每棵树,记录这棵树的高度(rank)。
  • 合并时如果两棵树的 rank 不同,那么从 rank 小的向 rank 大的连边。

uf-union-based-rank

此外,通过路径压缩,可以使得并查集更加高效。对于每个节点,一旦向上走到了一次根节点,就把这个点到父亲的边改为直接连向根。

uf-path-compress-1

在此之上,不仅仅是所查询的节点,在查询过程中向上经过的所有的节点,都改为直接连到根上。这样再次查询这些节点时,就可以很快知道根是谁了。

uf-path-compress-2

在使用这种简化的方法时,为了简单起见,即使树的高度发生了变化,我们也不修改 rank 的值。

并查集的复杂度

加入了这两个优化之后的并查集效率非常高。对 n 个元素的并查集进行一次操作的复杂度是 \(O(\alpha(n))\)。在这里,\(\alpha(n)\) 是阿克曼( Ackermann )函数的反函数。这比 \(O(log(n))\) 还要快。

不过,这是“均摊复杂度”。也就是说,并不是每一次操作都满足这个复杂度,而是多次操作之后平均每一次操作的复杂度是 \(O(\alpha(n))\) 的意思。

并查集的实现

下面是并查集的实现的例子。在例子中,我们用编号代表每个元素。数组 par 表示的是父亲的编号,par[x] = x 时, x 是所在的树的根。

路径压缩

1
2
3
4
5
6
7
8
9
10
11
class UnionFind:
def __init__(self, n: int):
self.par = list(range(n))

def find(self, x: int) -> int:
if self.par[x] != x:
self.par[x] = self.find(self.par[x])
return self.par[x]

def union(self, x: int, y: int) -> None:
self.par[self.find(x)] = self.find(y)

路径压缩 + 按秩(rank)合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class UnionFind:
# 初始化 n 个元素
def __init__(self, n: int):
self.par = list(range(n)) # 祖先结点
self.rank = [0] * n # 树的高度

# 查询树的根
def find(self, x: int) -> int:
if self.par[x] != x:
self.par[x] = self.find(self.par[x])
return self.par[x]

# 合并 x 和 y 所属的集合
def union(self, x: int, y: int) -> None:
x = self.find(x)
y = self.find(y)
if x == y:
return

if self.rank[x] < self.rank[y]:
self.par[x] = y
else:
self.par[y] = x
if self.rank[x] == self.rank[y]:
self.rank[x] += 1

References

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

<<挑战程序设计竞赛(第2版)>> 巫泽俊 2.4 并查集 p84-88