关于 并查集 - 代码实现与优化

关于并查集与离散数学直接的关系和并查集的抽象功能可以去看我之前的博客:

加上上一篇,这就是 并查集 的一切了。然后关于 并查集 的力扣题记录,之后可能会加上吧。

并查集的结构表示

并查集可以抽象成一个森林图,并且其中每棵树都是根数。比如以下图:

按理说,既然是树,那么使用树这种数据结构是在合适不过了。但是树因为涉及到多个对象互相持有引用,并且操作大都需要递归操作,效率会比较低。所以树是我们的最后手段,即能不用树表示就不用树来表示。

这里我们可以观察到,并查集虽然是一个森林图,但是它的结点个数是确定的,因为并查集的初始化需要传入容量,即等价关系中的 A 集合。

所以对于结点个数确定的根树,我们可以使用数组或者哈希表来表示。

具体如下:

1
2
3
4
定义一个数组或者哈希表 parent ,容量为 size 

parent[a] = b 当且仅当 b 是 a 的父亲
parent[a] = a 当且仅当 a 是根

例如上面的那个图:

如果用哈希表来表示:( 为了方便省略双引号 )

1
2
3
4
5
6
7
8
9
parent = {
a : a,
f : f,
b : a,
e : b,
c : a,
d : a,
g : f
}

其中:

  • a: a 表示 a 是根节点(父亲是自己的结点)
  • b: a 表示 a 是 b 的父亲

如果用数组来表示:

数组的话需要建立结点和数字间的函数关系:
首先定义对于结点 x ( x 为 char 类型)

其对应 索引 为 x - ‘a’

例如 a 就对应 0 , b 对应 1 以此类推。

则数组为( 数组里的数字从第0个数字开始 ):

1
parent = [0 ,0 ,0 ,0 ,1 ,5 ,5]
  • 第 0 个数 为 0 表示 索引 0 对应的结点 a 是根节点
  • 第 1 个数 为 0 表示 索引 1 对应的结点 b 的父亲是 0 对应的结点 a

表示完毕:

并查集代码实现

以上是一个特殊并查集的某个状态,实际上并查集只有容量这一个属性( 如果为哈希表的话则为 A 集合 )

并查集创建的时候,每一个结点都是孤立的,则这个关系为空集,当然空集也是等价关系。

然后并查集对外提供合并和查询两种操作,具体可以在上一篇看到:

代码:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class UnionFind{

vector<int> parent; // 数组

public:
/**
* 构造方法
* @param size 容量
* 初始化数组并把每个点的父节点都初始化为自己
*/
UnionFind(int size){
parent = vector<int>(size);
for (int i = 0 ; i < parent.size() ; i ++){
parent[i] = i;
}
}

/**
* 寻找所在树的 根节点
* @param x 操作结点
* 迭代寻找 x 的父亲,返回根节点
*/
int find(int x){
while(parent[x] != x){
x = parent[x];
}
return x;
}

/**
* 合并
* @param x
* @param y 合并的两个节点
* 把 x y 的根节点其中一个作为另一个的父亲
* 效果为 将 <x ,y> 加入关系中后取等价闭包
*/
void union_(int x, int y){
int rootX = find(x);
int rootY = find(y);
parent[rootX] = rootY;
}

/**
* 查询
* @param x
* @param y 要查询的两个节点
* 判断两个节点的根节点是否同一个 <=> 判断 <a ,b> 是否 ∈ R
*/
bool isConnected(int x ,int y){
int rootX = find(x);
int rootY = find(y);
return rootX == rootY;
}

};

并查集的效率优化

在 查询 和 合并 两个操作中,我们都需要获取到两个节点的根节点,则对于一次操作,时间复杂度为

1
2
3
4
5
6
7
8
o( 
max{
h(x),
h(y)
}
)

其中 h(x) 为 x 结点的高度

对于整个并查集,其时间复杂度为:o(H) ,H 为整个森林图的高度。

所以对于并查集的效率优化,简单来说就是要 尽量减少树的高度

路径压缩

路径压缩是在查询的操作中减少树的高度,因为整棵树的效果只取决于每个节点的根节点,所以只要结点的根节点不变,则效果不变。

隔代压缩

隔代压缩就是在查询根节点的时候,因为我们是迭代不断取 x 的父亲结点,我们可以在取到 x 的父亲结点之前,将 x 的父亲变成 原本 x 父亲的父亲,即:我变成我爷爷的儿子。

图解:

因为我们规定根节点的父亲是自己,所以过程中是不会出现空指针的,问题解决。

代码实现:(在寻找父节点的方法中添加)

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
* 寻找所在树的 根节点
* @param x 操作结点
* 迭代寻找 x 的父亲,返回根节点
*/
int find(int x){
while(parent[x] != x){
parent[x] = parent[parent[x]]; // 隔代压缩
x = parent[x];
}
return x;
}

完全压缩

完全压缩就好理解了,在寻找到一个节点的根节点后,将路径上所有节点的父亲都指定为根节点。

图解:

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
* 寻找所在树的 根节点
* @param x 操作结点
* 迭代寻找 x 的父亲,返回根节点
*/
int find(int x){
// 出口条件
if(parent[x] == x){
return x;
}
// 递操作
int root = find(parent[x]);

// 归操作
parent[x] = root;
return root;
}

可以看出,完全路径压缩虽好,但毕竟是递归啊。
递归的话系统需要跌栈,会占用额外的空间。
也可以说是一种空间换时间的方法啦。

两个压缩一般只能选取一个来使用,使用路径压缩后的并查集会有一种每查询一次都会优化的状态。在不断的查询中,能大大减少时间复杂度。

按秩合并

压缩操作可以在查询过程中优化,而在合并过程中,可以采用按秩合并的方式来优化。

之前讲过,合并的时候,实际上是找到 x 和 y 的根节点,然后把其中一个指定为另一个的父亲。那么这里到底是哪一个是另一个的父亲呢?

秉承着减少树高度的原则,我们可以指定让高度矮的树为高度高的树的儿子。

所以我们可以维护一个数组,数组里是每一个结点往下数到尽头的高度。

在合并的时候我们采用矮的为高的儿子的方式合并,并且合并后更新两个根节点的高度。

代码:

维护一个秩的数组,初始化为 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class UnionFind{

vector<int> parent;
vector<int> order; // 秩

public:
UnionFind(int size){
parent = vector<int>(size);
order = vector<int>(size ,1); // 初始化为 1
for (int i = 0 ; i < parent.size() ; i ++){
parent[i] = i;
}
}

// ……

}

合并的时候,按秩合并然后更新秩:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 合并
* @param x
* @param y 合并的两个节点
* 把 x y 的根节点其中一个作为另一个的父亲
* 效果为 将 <x ,y> 加入关系中后取等价闭包
*/
void union_(int x, int y){
int rootX = find(x);
int rootY = find(y);

// 按秩合并 ↓
if(order[rootX] < order[rootY]){
parent[rootX] = rootY;
}else{
parent[rootY] = rootX;
}

// 如果是两个秩小的合并为大的,则所有结点的秩不变
// 如果两个秩是一样然后合并,则作为父节点的秩要 +1
if(order[rootX] == order[rootY]){
order[rootX] ++;
}
}
  • 注意:这里我为啥不用树高度,而是用节点的秩呢? 因为我们更新秩的操作是在合并的操作中,如果你同时使用 路径压缩按秩合并 的话,这个 就不是指节点的高度了,或者说成假设所有查询操作都没进行的上一次合并后的结点高度更为合适。当然我们可以在 路径压缩 的过程中同时更新秩,但是那就造成了不必要的性能浪费, 陷入为了优化性能而占用更多性能的误区

  • 所以我这里干脆直接定义一个秩的概念,直接定义为假设所有查询操作都没进行的上一次合并后的结点高度。

最终优化

同时使用 按秩合并路径压缩 的并查集,其查询和合并的时间复杂度可以达到 o(1) ,因为在这种情况下树的高度一定小于或等于 2 ,即所有节点要不就是根节点要不就指向根节点。

  • 当然条件为初始化时候所有点都是孤立点,然后执行的合并操作都有按照按秩合并。

后记

以上就是有关并查集的一切,很多人不知道怎么去理解并查集这个东西。我则是直接把它理解为 离散数学 中的等价关系。

它可以解决以下问题:

已知集合 A 和 A 上的一个关系 R 。问 <a ,b> 是否 ∈ (R 的等价闭包 R’ )。