Fork me on GitHub

数据结构-并查集

并查集的概念

在计算机科学中,并查集是一种树形的数据结构,用于处理不交集的合并(union)及查询(find)问题.

并查集可用于查询网络中两个节点的状态, 这里的网络是一个抽象的概念, 不仅仅指互联网中的网络, 也可以是人际关系的网络、交通网络等.

并查集除了可以用于查询网络中两个节点的状态, 还可以用于数学中集合相关的操作, 如求两个集合的并集等.

并查集对于查询两个节点的连接状态非常高效.对于两个节点是否相连,也可以通过求解查询路径来解决, 也就是说如果两个点的连接路径都求出来了,自然也就知道两个点是否相连了,但是如果仅仅想知道两个点是否相连,使用路径问题来处理效率会低一些,并查集就是一个很好的选择.

https://www.cnblogs.com/xzxl/p/7226557.html

https://blog.csdn.net/huisekonghuan/article/details/79288550

并查集的实现

并查集(Union Find)是一种树形的数据结构,它是专门用来处理不相交集合的合并及查询问题的,它主要支持两个操作,一个是union操作,即将两个不相交的集合的合并,另一个是find操作,即查找该元素属于哪一个集合,以此衍生出来的一个操作是isConnected,也就是判断两个元素是否连接,即是否同属于一个集合中.

基本结构

创建一个UF接口

1
2
3
4
5
6
public interface UF {

int getSize();
boolean isConnected(int p, int q);
void unionElements(int p, int q);
}

Quick Find方式实现

想要实现快查, 就需要只有一个领头的
实现接口方法

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
public class UnionFind1 implements UF {
private int[] id; // 我们的第一版Union-Find本质就是一个数组

public UnionFind1(int size) {

id = new int[size];

// 初始化, 每一个id[i]指向自己, 没有合并的元素
for (int i = 0; i < size; i++)
id[i] = i;
}

@Override
public int getSize(){
return id.length;
}

// 查找元素p所对应的集合编号
// O(1)复杂度
private int find(int p) {
if(p < 0 || p >= id.length)
throw new IllegalArgumentException("p is out of bound.");

return id[p];
}

// 查看元素p和元素q是否所属一个集合
// O(1)复杂度
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}

// 合并元素p和元素q所属的集合
// O(n) 复杂度
@Override
public void unionElements(int p, int q) {

int pID = find(p);
int qID = find(q);

if (pID == qID)
return;

// 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
for (int i = 0; i < id.length; i++)
if (id[i] == pID)
id[i] = qID;
}
}

从上面的实现的并查集我们知道,查询的时间复杂度为 O(1) ,合并的时间复杂度为 O(n),如果数据量一大 O(n) 复杂度就显得很慢了. 下面我们就来优化下上面实现的并查集.

Quick Union 实现

通过树形结构来描述节点之间的关系,底层存储通过数组来存储.

以前我们介绍到树都是父节点指向子节点的,这里我们是通过子节点来指向父节点,根节点指向它自己.

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
public class UnionFind2 implements UF {
// 第二版Union-Find, 使用一个数组构建一棵指向父节点的树
// parent[i] 表示元素所指向的父节点
private int[] parent;

// 构造函数
public UnionFind2(int size){

parent = new int[size];

// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < size ; i ++ )
parent[i] = i;
}

@Override
public int getSize(){
return parent.length;
}

// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");

// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while(p != parent[p])
p = parent[p];
return p;
}

// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}

// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
@Override
public void unionElements(int p, int q){

int pRoot = find(p);
int qRoot = find(q);

if( pRoot == qRoot )
return;

parent[pRoot] = qRoot;
}
}

测试

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
import java.util.Random;


public class Main {

private static double test(UF uf, int m) {

long startTime = System.nanoTime();
Random random = new Random();
for (int i = 0; i < m; i++) {
int p = random.nextInt(uf.getSize());
int q = random.nextInt(uf.getSize());
uf.unionElements(p, q);
}

for (int i = 0; i < m; i++) {
int p = random.nextInt(uf.getSize());
int q = random.nextInt(uf.getSize());
uf.isConnected(p, q);
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}


public static void main(String[] args) {
int size = 100000; //元素个数
int p = 10000; //操作次数
double countTime1 = test(new UnionFind1(size), p);
double countTime2 = test(new UnionFind2(size), p);
System.out.println("countTime1 = " + countTime1);
System.out.println("countTime2 = " + countTime2);
System.out.println("Hello World!");
}
}

输出结果

1
2
3
countTime1 = 0.3364559
countTime2 = 0.0037194
Hello World!

将操作次数扩大10倍再次进行测试, 结果如下

1
2
3
countTime1 = 6.9038054
countTime2 = 15.7183732
Hello World!

发现Quick Union版本的并查集比Quick Find版本的并查集慢很多.
这是因为对于Quick Find的并查集查询的操作时间复杂度为O(1),Quick Union的合并和查询都是O(h),并且生成的树深度可能很深.

下面就对 Quick Union 版本的并查集进行优化.

基于size的优化

上面Quick Union版本的并查集基于树形结构实现的,但是没有对树的高度进行任何优化和限制,所以导致在上面的性能比对中Quick Union的并查集性能很差.最坏的情况下. 该树形结构会变成链式结构,此时find操作退化成了O(n).
在该版本的优化中,我们是对union操作进行优化,之前我们在做union操作时没有判断哪一方节点数更多,那么我们现在把这一判断加上,即在合并前先判断哪一方树的子节点数多,那么我们把子节点数少的一方附加在子节点数多的一方就可以了.

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
56
57
58
59
60
61
62
63
64
public class UnionFind3 implements UF {
private int[] parent; // parent[i]表示第一个元素所指向的父节点
private int[] sz; // sz[i]表示以i为根的集合中元素个数

// 构造函数
public UnionFind3(int size) {

parent = new int[size];
sz = new int[size];

// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for (int i = 0; i < size; i++) {
parent[i] = i;
sz[i] = 1;
}
}

@Override
public int getSize() {
return parent.length;
}

// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find(int p) {
if (p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");

// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while (p != parent[p])
p = parent[p];
return p;
}

// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}

// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
@Override
public void unionElements(int p, int q) {

int pRoot = find(p);
int qRoot = find(q);

if (pRoot == qRoot)
return;

// 根据两个元素所在树的元素个数不同判断合并方向
// 将元素个数少的集合合并到元素个数多的集合上
if (sz[pRoot] < sz[qRoot]) {
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
} else { // sz[qRoot] <= sz[pRoot]
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
}

将这个优化后的方法进行测试,结果如下

1
2
3
4
5
6
7
8
int size = 100000; //元素个数
int p = 100000; //操作次数


countTime1 = 7.0184373
countTime2 = 14.5064005
countTime3 = 0.026344
Hello World!

基于rank的优化

上面基于size的优化方案,是节点数少的树往节点数多的树合并,但是节点数多不代表树的高度
高.
我们来考虑这么一种情况,假如我们现在要合并的两个元素p和q,p元素的子节点数远大于q节点的子节点数,但是,这p这棵树的深度只有1,而q的深度等于节点数,而按照我们的size优化,我们是把q加在了p上,但其实应该是p加在q上,因为虽然q的子节点多,但它的深度小.这样树的深度更少,搜索起来就更快了.

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
56
57
58
59
60
61
62
63
64
65
public class UnionFind4 implements UF{
private int[] rank; // rank[i]表示以i为根的集合所表示的树的层数(深度)
private int[] parent; // parent[i]表示第i个元素所指向的父节点

// 构造函数
public UnionFind4(int size){

rank = new int[size];
parent = new int[size];

// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < size ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}

@Override
public int getSize(){
return parent.length;
}

// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");

// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while(p != parent[p])
p = parent[p];
return p;
}

// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}

// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
@Override
public void unionElements(int p, int q){

int pRoot = find(p);
int qRoot = find(q);

if( pRoot == qRoot )
return;

// 根据两个元素所在树的rank不同判断合并方向
// 将rank低的集合合并到rank高的集合上
if(rank[pRoot] < rank[qRoot])
parent[pRoot] = qRoot;
else if(rank[qRoot] < rank[pRoot])
parent[qRoot] = pRoot;
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // 此时, 维护rank的值
}
}
}

注意此处因为增加的是rank,即树的深度,而当一棵树的深度小于另一棵的时候,我们将深度小的加到深度大的上,附加后整棵树的深度是不变的,还是原来深度较大的那棵树的深度!只有两棵树深度一样的时候,在附加是才需要将深度加一.

路径压缩优化

​ 前两种优化我们都是在union操作中进行的,那我们可否在find里面进行优化呢?当然可以,这就是路径压缩的优化点.我们在对元素做find操作的时候,如果该元素的父节点不是自己,那么,我们将该元素的父节点更改为父节点的父节点,形象点说就是,将该节点的爷爷变成了自己的父亲,这样在下一次find的时候就跳过了该节点的父节点.

以上步骤看似很复杂,但是实现上只需要添加一行代码.

1
2
3
4
5
6
7
8
9
10
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");

while( p != parent[p] ){
parent[p] = parent[parent[p]]; //添加的一行代码,该行代码就表示将p节点父亲的父亲变为p的父亲.
p = parent[p];
}
return p;
}

另外一种压缩方式, 直接将树压缩成两层
让节点的父亲直接指向最顶层的元素

1
2
3
4
5
6
7
8
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");

if(p != parent[p])
parent[p] = find(parent[p]);
return p;
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
// int size = 100000; //元素个数
// int p = 100000; //操作次数



countTime1 = 7.0340682
countTime2 = 13.9094047
countTime3 = 0.0229193
countTime4 = 0.018054
countTime5 = 0.015297
countTime6 = 0.017712
Hello World!

时间复杂度分析

在我们使用Quick Union版本的并查集使用树形结构来组织节点的关系.
那么性能跟树的深度有关系,简称O(h),以前介绍二分搜索树的时候,时间复杂度也是为O(h).
但是并查集并不是一个二叉树,而是一个多叉树,所以并查集的查询和合并时间复杂度并不是O(log n)
在加上rank和路径压缩优化后 ,并查集的时间复杂度为O(log* n)

完整代码

-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!
0%