• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

并查集-Java实现

开发技术 开发技术 2个月前 (11-28) 18次浏览

并查集
借鉴百度百科的解释,并查集就是在一些有N个元素的集合问题中,开始的时候让每个元素成为自己的集合,然后按照一定的顺序将属于同一组的元素所在的集合进行合并(合并的是集合),在合并的期间需要方法查找元素所在的集合。并查集的原理比较简单,解决的问题的特点是看似并不复杂,但数据量极大。例如:图的连通子图问题,一个图里面有几个连通子图,判断这幅图是否连通等。若用正常的数据结构来描述,往往时空复杂度会过高。并查集是一种树形数据结构,用于处理一些不相交集合的合并和查询问题。并查集的原理就是朋友的朋友就是我的朋友。
基本
正如名字表达的那样,并查集需要合并和查询集合,所以并查集一般需要一个数组和两个函数:int[] parent, int find(int element)和void unionElements(int firstOne, int secondOne)。
parent数组用来记录每个元素的前导点,也就是确定该元素所在的集合id;find函数用来查找某元素所在的集合id;unionElements用来合并不同的集合。其基本过程如下图所示。
并查集-Java实现
实现代码:

public class UnionFind1 {
    private int[] id; //存储元素的root
    private int size; //并查集大小
    //构建新的并查集
    public UnionFind1(int size) {
        this.size = size;
        id = new int[size];
        for (int i=0; i<size; i++)
            id[i] = i; //每个元素都指向自己
    }
    //查看元素所属的集合
    public int find(int element) {
        return id[element];
    }
    //判断是否属于同一集合
    public boolean isConnected(int firElement, int secElement) {
        return find(firElement) == find(secElement);
    }
    //合并两个集合
    public void unionElements(int firElement, int secElement) {
        int firUnion = find(firElement);
        int secUnion = find(secElement);
        if(firUnion != secUnion) {
            //合并效率低下,合并一次是O(n)的复杂度
            for(int i=0; i<this.size; i++) {
                if(id[i] == firUnion) {
                    id[i] = secUnion;
                }
            }
        }
    }
    //打印元素
    private void printSet() {
        for (int id : this.id)
            System.out.print(id + " ");
        System.out.println();
    }
    //入口
    public static void main(String[] args) {
        int n = 10;
        UnionFind1 union = new UnionFind1(n);
        System.out.println("初始化: ");
        union.printSet();

        System.out.println("连接5 6");
        union.unionElements(5, 6);
        System.out.println("连接1 2 ");
        union.unionElements(1, 2);
        System.out.println("连接2 3");
        union.unionElements(2, 3);
        System.out.println("连接1 4");
        union.unionElements(1, 4);
        System.out.println("连接1 5");
        union.unionElements(1, 5);

        System.out.println("最终结果: ");
        union.printSet();

        System.out.println("1 6 是否连接: " + union.isConnected(1, 6));
        System.out.println("1 8 是否连接: " + union.isConnected(1, 8));
        System.out.println("1 4 是否连接: " + union.isConnected(1, 4));
    }
}
Output:
初始化: 
0 1 2 3 4 5 6 7 8 9 
连接5 6
连接1 2 
连接2 3
连接1 4
连接1 5
最终结果: 
0 6 6 6 6 6 6 7 8 9 
1 6 是否连接: true
1 8 是否连接: false
1 4 是否连接: true

优化1
上述的并查集合并时候的复杂度是O(n)的,现在对其改进,在合并的时候,当前集合的爸爸去当别人的儿子,当前集合其他元素的爸爸(前导点)不变,这样的话,需要改变查找的方式,因为对某个集合来说,最终的爸爸只有一个。例如对于下面这个数组集合:
元素:0 1 2 3
爸爸:1 2 3 3
查找元素0和1的”爸爸”,应该是3而不是1和2,所以find的寻找方式应该改变,应该找到最终的爸爸(元素和爸爸是同一个的点)。这种方式合并的复杂度下降了,但是find的复杂度增加了。
实现代码:

public class UnionFind2 {
    private int[] id;
    private int size;
    public UnionFind2(int size) {
        this.size = size;
        id = new int[size];
        for (int i=0; i<size; i++)
            id[i] = i;
    }
    //找到最终的root
    public int find(int element) {
        while(element != id[element])
            element = id[element];
        return element;
    }
    public boolean isConnected(int firElement, int secElement)
    { return find(firElement) == find(secElement); }
    public void unionElements(int firElement, int secElement) {
        int firUion = find(firElement);
        int secUion = find(secElement);
        if (firUion == secUion)
            return;
        id[firUion] = secUion;
    }
    private void printSet() {
        for (int id : this.id)
            System.out.print(id + " ");
        System.out.println();
    }
    public static void main(String[] args) {
        int n = 10;
        UnionFind2 union = new UnionFind2(n);
        System.out.println("初始化: ");
        union.printSet();

        System.out.println("连接5 6");
        union.unionElements(5, 6);
        System.out.println("连接1 2 ");
        union.unionElements(1, 2);
        System.out.println("连接2 3");
        union.unionElements(2, 3);
        System.out.println("连接1 4");
        union.unionElements(1, 4);
        System.out.println("连接1 5");
        union.unionElements(1, 5);

        System.out.println("最终结果: ");
        union.printSet();

        System.out.println("1 6 是否连接: " + union.isConnected(1, 6));
        System.out.println("1 8 是否连接: " + union.isConnected(1, 8));
        System.out.println("1 4 是否连接: " + union.isConnected(1, 4));
    }
}
Output:
初始化: 
0 1 2 3 4 5 6 7 8 9 
连接5 6
连接1 2 
连接2 3
连接1 4
连接1 5
最终结果: 
0 2 3 4 6 6 6 7 8 9 
1 6 是否连接: true
1 8 是否连接: false
1 4 是否连接: true

优化2
优化1的修改方案,是牺牲查询函数的复杂度来换取合并函数复杂度的下降,并且还有引入一个新的问题,就是合并后的数组很可能会达到线性链表的状态,例如:
元素:0 1 2 3 4 5 6 7 8 9
爸爸:1 2 3 4 5 6 7 8 9 9
这样画出来的连通子图是一条链表来的,这种原因是合并方式不合理造成的。所以第二种优化的方式可从合并方式下手,引入一个权重来衡量到底谁应该当爸爸。有两种权重可供选择,一种是重量,一种是高度。
重量(数目):就是集合爸爸底下有多少数目的子孙;高度(代,箭头数):就是集合爸爸底下有多少代子孙。
基于重量,谁重谁当爸爸。
实现代码:

public class UnionFind3 {
    private int[] id;
    private int[] weight;
    private int size;
    public UnionFind3(int size) {
        this.size = size;
        this.id = new int[size];
        this.weight = new int[size];
        for (int i=0; i<size; i++) {
            this.id[i] = i;
            this.weight[i] = 1; //初始化为1个元素
        }
    }
    public int find(int element) {
        while(element != id[element]){
            element = id[element];
        }
        return element;
    }
    public boolean isConnected(int firElement, int secElement) {
        return find(firElement) == find(secElement);
    }
    public void unionElements(int firElement, int secElement) {
        int firUion = find(firElement);
        int secUion = find(secElement);
        if(firUion == secUion)
            return;
        //减少find的查找时间,谁重谁是爸爸
        if(weight[firUion] > weight[secUion]) {
            id[secUion] = firUion;
            weight[firUion] += weight[secUion];
        }
        else {
            id[firUion] = secUion;
            weight[secUion] += weight[firUion];
        }
    }
    private void printSet() {
        for (int id : this.id)
            System.out.print(id + " ");
        System.out.println();
    }
    public static void main(String[] args) {
        int n = 10;
        UnionFind3 union = new UnionFind3(n);
        System.out.println("初始化: ");
        union.printSet();

        System.out.println("连接5 6");
        union.unionElements(5, 6);
        System.out.println("连接1 2 ");
        union.unionElements(1, 2);
        System.out.println("连接2 3");
        union.unionElements(2, 3);
        System.out.println("连接1 4");
        union.unionElements(1, 4);
        System.out.println("连接1 5");
        union.unionElements(1, 5);

        System.out.println("最终结果: ");
        union.printSet();

        System.out.println("1 6 是否连接: " + union.isConnected(1, 6));
        System.out.println("1 8 是否连接: " + union.isConnected(1, 8));
        System.out.println("1 4 是否连接: " + union.isConnected(1, 4));
    }
}
Output:
初始化: 
0 1 2 3 4 5 6 7 8 9 
连接5 6
连接1 2 
连接2 3
连接1 4
连接1 5
最终结果: 
0 2 2 2 2 6 2 7 8 9 
1 6 是否连接: true
1 8 是否连接: false
1 4 是否连接: true

基于高度,谁子孙代数多谁当爸爸。
实现代码:

public class UnionFind4 {
    private int[] id;
    private int[] height;
    private int size;
    public UnionFind4(int size) {
        this.size = size;
        this.id = new int[size];
        this.height = new int[size];
        for (int i=0; i<size; i++) {
            id[i] = i;
            height[i] = 1;
        }
    }
    public int find(int element) {
        while(element != id[element])
            element = id[element];
        return element;
    }
    public boolean isConnected(int fir, int sec) {
        return find(fir) == find(sec);
    }
    public void unionElements(int fir, int sec) {
        int firUion = find(fir);
        int secUion = find(sec);
        if(firUion == secUion)
            return;
        //使用高度决定谁被谁插入,减少find的时间
        if(height[firUion] > height[secUion])
            id[secUion] = firUion;
        else if(height[firUion] < height[secUion])
            id[firUion] = secUion;
        else {
            id[firUion] = secUion;
            height[secUion]++;
        }
    }
    private void printSet() {
        for (int id : this.id)
            System.out.print(id + " ");
        System.out.println();
    }
    public static void main(String[] args) {
        int n = 10;
        UnionFind4 union = new UnionFind4(n);
        System.out.println("初始化: ");
        union.printSet();

        System.out.println("连接5 6");
        union.unionElements(5, 6);
        System.out.println("连接1 2 ");
        union.unionElements(1, 2);
        System.out.println("连接2 3");
        union.unionElements(2, 3);
        System.out.println("连接1 4");
        union.unionElements(1, 4);
        System.out.println("连接1 5");
        union.unionElements(1, 5);

        System.out.println("最终结果: ");
        union.printSet();

        System.out.println("1 6 是否连接: " + union.isConnected(1, 6));
        System.out.println("1 8 是否连接: " + union.isConnected(1, 8));
        System.out.println("1 4 是否连接: " + union.isConnected(1, 4));
    }
}
Output:
初始化: 
0 1 2 3 4 5 6 7 8 9 
连接5 6
连接1 2 
连接2 3
连接1 4
连接1 5
最终结果: 
0 2 6 2 2 6 6 7 8 9 
1 6 是否连接: true
1 8 是否连接: false
1 4 是否连接: true

优化3
不管是基于重量还是高度,并查集还是有可能会出现深的节点,这时候可以进行干预,进行路径压缩,具体的方法就是在每一步的查询操作进行压缩,让当前元素的”爸爸”升级成”爷爷”,这种路径压缩只能在基于重量的并查集实现,因为在压缩的时候,当前集合的重量是不会变的,但是高度很有可能改变。
实现代码:

public class UnionFind5 {
    private int[] id;
    private int[] weight;
    private int size;
    public UnionFind5(int size) {
        this.size = size;
        this.id = new int[size];
        this.weight = new int[size];
        for (int i=0; i<size; i++) {
            id[i] = i;
            weight[i] = 1;
        }
    }
    //路径压缩,指向自己爸爸的爸爸,进一步压缩
    public int find(int element) {
        while(element != id[element]) {
            id[element] = id[id[element]];
            element = id[element];
        }
        return element;
    }
    public boolean isConnected(int fir, int sec) {
        return find(fir) == find(sec);
    }
    public void unionElements(int fir, int sec) {
        int firUion = find(fir);
        int secUion = find(sec);
        if (firUion == secUion)
            return;
        if (weight[firUion] > weight[secUion]) {
            id[secUion] = firUion;
            weight[firUion] += weight[secUion];
        }
        else {
            id[firUion] = secUion;
            weight[secUion] += weight[firUion];
        }
    }
    private void printSet() {
        for (int id : this.id)
            System.out.print(id + " ");
        System.out.println();
    }
    public static void main(String[] args) {
        int n = 10;
        UnionFind5 union = new UnionFind5(n);
        System.out.println("初始化: ");
        union.printSet();

        System.out.println("连接5 6");
        union.unionElements(5, 6);
        System.out.println("连接1 2 ");
        union.unionElements(1, 2);
        System.out.println("连接2 3");
        union.unionElements(2, 3);
        System.out.println("连接1 4");
        union.unionElements(1, 4);
        System.out.println("连接1 5");
        union.unionElements(1, 5);

        System.out.println("最终结果: ");
        union.printSet();

        System.out.println("1 6 是否连接: " + union.isConnected(1, 6));
        System.out.println("1 8 是否连接: " + union.isConnected(1, 8));
        System.out.println("1 4 是否连接: " + union.isConnected(1, 4));
    }
}
Output:
初始化: 
0 1 2 3 4 5 6 7 8 9 
连接5 6
连接1 2 
连接2 3
连接1 4
连接1 5
最终结果: 
0 2 2 2 2 6 2 7 8 9 
1 6 是否连接: true
1 8 是否连接: false
1 4 是否连接: true

这篇博客主要是方便自己日后复习和查看使用,主要参考了下面这篇博客:
https://www.cnblogs.com/noKing/p/8018609.html
下面还有一篇关于并查集的概念解释得不错的概念分享给大家:
https://www.cnblogs.com/-new/p/6662301.html
谢谢大家,这是本人的第一篇技术博客,欢迎大家批评指正,转载注明出处就行。


喜欢 (0)