概念
- 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题
- 有两个比较和核心的功能
- Find:查询一个元素在那个集合
- Union:合并两个集合
- 并查集的重要思想是把集合的其中一个元素作为这个集合代表元素
例子
假设有N个员工,同时可以知道类似A员工与B员工是同事、C与D同事、A与E是同事...这样的数据
现在任取两个员工,如果快速的判断这两个员工是否为同事?
再比如如何知道员工们有几个公司?
这里就需要引入并查集这个数据结构.
把所有人划分到若干个不相交的公司(集合)中，每个公司里的人彼此是同事。为了判断两个人是否为同事，只需看它们是否属于同一个公司即可
用具体的数据进行展示
现有8名员工,员工按0-7编号,同事关系为[1,3],[2,4],[3,5],[1,6],[0,2],[5,6]
首先先按每个员工都有一个自己的公司,公司的员工只有自己,自己是公司的代表员工
翻译一下就是,把每个元素视为一个只有自己的集合,自身即为集合的代表元素
用一个数组记录每个员工所在公司的代表员工,数组下标与员工编号相对应,值是代表员工的员工编号
得到数组 :[0,1,2,3,4,5,6,7]
这个数组就是并查集
接着遍历同事关系信息.
第一个是[1,3],然后把1号员工所在公司的代表员工和3号员工所在公司的代表员工改成同一个
得到数组 :[0,1,2,1,4,5,6,7]
用代码表示就是:
public void merge(int x, int y)
{
fa[x] =y;
}
merge(1,3);
处理[2,4]
得到数组 :[0,1,2,1,2,5,6,7]
逐一处理
[0,1,2,1,2,1,6,7]
[0,1,2,1,2,1,1,7]
[0,1,0,1,2,1,1,7]
[0,1,0,1,2,1,1,7]
借助这个数组,就可以试着判断两个员工是否为同事了
如员工1,员工5,在数组中拿到他们的所在公司的代表员工,都是员工1,说明是1和5是同事
员工6,员工7,代表员工不一致,不是同事
但这样是有问题的,并查集是树状结构,需要溯源后才能确定
比如员工2和员工4,代表是0与2,看似不一样.
但员工4的代表员工是员工2,员工2→员工0.实际上员工2和员工4都指向员工0.
也就是说,除非所在公司的代表员工是自己,否则都需要往上溯源,才能确定实际的代表员工
这样会产生额外的处理步骤,因此,可以在发现员工4的实际代表员工是员工0时,应该直接把员工4的代表员工设置为0.
进行路径的压缩.
到此,就可以写出判断两个同事是否处于一个公司的代码了
public int find(int x)
{
if(x == fa[x])
return x; //代表元素等同于当前元素
else{
fa[x] = find(fa[x]); //向上溯源,并把根元素设置为代表元素
return fa[x]; //返回代表元素
}
}
以上代码一般简写为一行：
public int find(int x)
{
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
重新去看前面提到的根据同事关系对数组的处理,也可以对代码进行一些优化:
直接对根元素进行处理.
public void merge(int x, int y)
{
//获取根元素
int fx=find(x);
int fy=find(y);
if(fx!= fy) { //如果不属于同一个集合
fa[fx] = fy; //合并它们
}
}
代码可简写为:
public void merge(int x, int y)
{
fa[find(x)] =find(y);
}
并查集优化-按秩合并
即使在find的时候进行了一下处理,但在实际使用时,并查树仍然是一个树型结构,难免有一些的递归上的消耗.
可以采取牺牲空间复杂度的方式
树型结构的层级加高只会在合并的时候发生.
考虑一下,在什么情况下,可以避免合并时层级加高.
在两个层级不一样时,低层级合并到高层级代表元素之下,不会加高层级.
如一个并查集[0,0,2]
现在要合并merge(0,2)
按原来的方式,就是把2作为0的代表元素,也就是把0合并到2之下,结果是:[2,0,2];
那在进行find(1)时,就要向上递归2次才能拿到代表元素2
如果按把2合并的0之下,那结果就是[0,0,0],这就是一个层级最小的并查集了
因此需要做些处理,记录每个元素的层级,在合并时进行判断,低层级合并到高层级
同样的,用一个数组记录元素的层级信息.
public void merge(int x, int y)
{
//获取根元素
int fx=find(x);
int fy=find(y);
if(fx!= fy) { //如果不属于同一个集合
//根据层级判断怎么合并
if (rank[x] <= rank[y]){
fa[fx] =fy;
rank[y]++;
}else{
fa[fy] = fx;
}
}
}
最终整合为一个类
class DisjointSetUnion {
int[] fa;
int[] rank;
int n;
public DisjointSetUnion(int n) {
this.n = n;
this.rank = new int[n];
this.fa = new int[n];
for (int i = 0; i < n; i++) {
this.fa[i] = i;
this.rank[i] = 1;
}
}
public int find(int x) {
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
public void merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
if (rank[x] <= rank[y]) {
fa[fx] = fy;
rank[y]++;
} else {
fa[fy] = fx;
}
}
}
}
