并查集 — Java语言实现_set createset(int size)

一、概述

用一个数组来储存各个集合中的元素，每个集合都有自己的树根结点。

例如：

//共有两个集合。分别是[2,3,4]，集合的树根结点为2；和[1],集合的树根结点为1
disjointSet[3] = 2;//结点3的父结点为2
disjointSet[4] = 2;
disjointSet[2] = -1;//结点2是根结点
disjointSet[1] = -1
1
2
3
4
5

二、底层

// 这里默认数组从下标1开始储存
int[] disjointSet;//储存各个集合元素
int size;//元素总个数
1
2
3

三、初始化

实例化数组，并默认数组中的结点都是根结点

public void create(){
	disjointSet = new int[size+1];
	for(int i = 1; i <= size; i++){
		disjointSet[i] = -1;//
	}
}
1
2
3
4
5
6

四、查

找到结点x所在集合的树根结点

public int find(int x){
	for(; disjointSet[x] >= 0; x = disjointSet[x]);
	return x;
}
1
2
3
4

五、并

把两个结点所在的集合合并，即合并两个结点所在集合的树根结点

public void unionSet(int x,int y){
	x = find(x);//找到x结点所在集合的树根结点
	y = find(y);
	disjointSet[x] = y;//把x集合合并到y集合中去
}
1
2
3
4
5

六、并的优化 — 按规模并

如果一直进行合并，那么这个集合树会越来越大，find方法的时间复杂度会越来越大。所以我们可以按规模或树高合并，把小的集合合并到大的集合中去，这样树高就不会一直变大了。

集合的规模可以用根结点来显示，例如disjointSet[2] = -3,代表以2为树根结点的集合共有3个结点

public void unionSet(int x,int y){
	x = find(x);
	y = find(y);
	if(disjointSet[x] < disjointSet[y]){
		disjointSet[x] += disjointSet[y];
		disjointSet[y] = x;
	}else{
		disjointSet[y] += disjointSet[x];
		disjointSet[x] = y;
	}
}
1
2
3
4
5
6
7
8
9
10
11

七、查的优化 — 路径压缩

当集合树较高时，在底层的结点查找会耗费较多时间。我们可以在一次查找中，把查找结点到根结点路径中的所有结点的父结点都改为根结点。这样虽然我们在第一次查找会耗费较多时间，但多次查找时，可以节省大量时间。

public int find(int x){
	if(disjointSet[x] < 0){
		return x;
	}
	disjointSet[x] = find(disjointSet[x]);
	return disjointSet[x];
}
1
2
3
4
5
6
7