并查集基础知识

发表于 | 浏览 次

并查集(不相交集合)

不相交集合数据结构是这样一种数据结构: 它维护了一个不相交动态集的集合

$$
S = {s_1, s_2, …, s_i, …, s_k}
$$
对于每个集合S中的每个元素集合si而言,用集合中的而一个元素来代表该集合.假设x是集合si中的一个元素,则有以下三种操作:

make_set(x): 建立一个新的集合,它的唯一成员是x.因为各个集合是不相交的集合, 所以x不会出现在别的集合中.
union(x, y): 将包含x和y的两个动态集合(表示为sx和sy合并成一个新的集合, 即这两个集合的并集)
find_set(x): 返回一个指针,该指针指向包含x的(唯一)集合的代表.
不相交集合可以用于求无向图的连通分量等.待后续加上代码

为了提交效率,建立并查集的过程往往会采用两种策略来提高性能.一种是按秩(秩是指节点高度的一个上界)合并, 另一种是路径压缩.
按秩合并是在合并两个集合的过程中, 让具有较小秩的根指向较大秩的根.
路径压缩是在查找节点的根节点的过程中, 使查找路径上的每个节点指向指向根(即令根节点成为查找路径上每个节点的父节点).

节点x的秩: 节点x的高度(从节点x到某一后代叶节点的最长简单路径上边的数目)的一个上界.
当make_set(x)创建一个单元素x集合时, 节点x的秩为0.
使用按秩合并union(x, y)合并两个集合时, 若两个集合的秩不同,则让较大秩的根成为较小秩的根的父节点, 秩本身保持不变.若两个集合的秩相同,则任意选择两个根中的一个作为父节点, 并使它的秩加1.

并查集的实现(伪代码)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
make_set(x)
    x.p = x     // x的父节点是自己,即x是x所在集合的根节点
    x.rank = 0 // x.rank即x的秩

link(x, y)
    if(x.rank > y.rank)
        y.p = x
    else
        x.p = y
        if(x.rank == y.rank)
            y.rank = y.rank + 1
union(x, y)
    link(find_set(x), find_set(y))

find_set(x)
    if x != x.p
    	x.p = find_set(x.p)
    return x.p

find_set的非递归形式

1
2
3
4
5
6
7
8
find_set(x)
    a = x
    while x != x.p
    	x = x.p
    while a != a.p
    	z = a
    	a = a.p
    	z.p = x