java 并查集 学习笔记

概念

• 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题
• 有两个比较和核心的功能
  • 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;
            }
        }
    }
}