通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

算法学习之并查集

9706人浏览 / 11人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  这些算法有自己的方法  | 

作者:因情语写

链接:https://proprogrammar.com/article/383

声明:请尊重原作者的劳动,如需转载请注明出处


    写在前面

    本人抱着学习的目的写这篇文章,本人算法水平有限,在接触了相关概念,并动手操作过,看了相关的资料以后,对所学习内容做一个记录,其实主要就是拼凑看过的文章中的内容,起一个备忘的作用,如有错误,不全,幼稚的地方,还请见谅。

    用途

    并查集是一种数据结构, 常用于描述集合,经常用于解决此类问题:某个元素是否属于某个集合,或者某个元素和另一个元素是否同属于一个集合

    解释

    即有一些元素,把这些元素分组,组内元素是相互关联的,形成一棵树形结构,不同的组在一起形成森林

    有两个概念:

    weight:即一个分组中元素的数量

    height:即一个分组形成的树的高度

    有两个操作:

    find:找一个元素所在分组的根元素

    注:find操作中还可以进行路径压缩

    union:合并两个元素所在的分组为一个分组

    附加操作:

    计算分组的数量

    判断两个元素是否位于同一分组

    具体代码

    下面看一下具体的算法,重点代码有相应注释

public class UnionFind
{
	private int[] parent;
    private int size;
 
    // 设定并查集大小并初始化
    public UnionFind(int size) {
        this.size = size;
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            // 每个元素都指向自己,即自己和自己一组
            parent[i] = i;
        }
    }
     
    // 查找分组的根结点
    public int find(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }
 
    // 判断是否属于同一分组,如果根相同即属于同一分组
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    // 合并两个元素的分组
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
        if (firstRoot == secondRoot) {
            return;
        }
       
        // 分组不同,将其中一个分组的根作为另一个分组的根
        parent[firstRoot] = secondRoot;
    }
 
    /**
     * 本并查集使用数组实现,为了更直观地看清内部数据,采用打印数组
     */
    private void printArr() {
        for (int parent : this.parent) {
            System.out.print(parent + "\t");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);
        System.out.println("初始:");
        union.printArr();
 
        System.out.println("连接了5 6");
        union.unionElements(5, 6);
        union.printArr();
 
        System.out.println("连接了1 2");
        union.unionElements(1, 2);
        union.printArr();
 
        System.out.println("连接了2 3");
        union.unionElements(2, 3);
        union.printArr();
 
        System.out.println("连接了1 4");
        union.unionElements(1, 4);
        union.printArr();
 
        System.out.println("连接了1 5");
        union.unionElements(1, 5);
        union.printArr();
 
        System.out.println("1  6 是否连接:" + union.isConnected(1, 6));
        System.out.println("1  8 是否连接:" + union.isConnected(1, 8));
    }

    上面是基本的算法,在进行两个分组合并的时候没有做特殊处理,可以进行两种处理,把weight小的分组的根节点连接到weight大的分组的根结点上,或者把height小的分组的根结点连接到height大的分组的根结点上,下面来看一下这两种情况

    使用weight的情况

public class UnionFind {
    private int[] parent;
    private int[] weight;
    private int size;
 
    public UnionFind(int size) {
        this.parent = new int[size];
        this.weight = new int[size];
        this.size = size;
        // 在初始化分组的同时也初始化weight
        for (int i = 0; i < size; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }
 
    public int find(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }
 
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
 
        // 如果已经属于同一个集合了,就不用再合并了。
        if (firstRoot == secondRoot) {
            return;
        }
 
        // 将weight小的分组连接到weight大的分组上
        if (weight[firstRoot] > weight[secondRoot]) {
            parent[secondRoot] = firstRoot;
            weight[firstRoot] += weight[secondRoot];
        } else {//weight[firstRoot] <= weight[secondRoot]
            parent[firstRoot] = secondRoot;
            weight[secondRoot] += weight[firstRoot];
        }
    }
 
    private void printArr(int[] arr){
        for(int p : arr){
            System.out.print(p+"\t");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);
 
        System.out.println("初始parent:");
        union.printArr(union.parent);
        System.out.println("初始weight:");
        union.printArr(union.weight);
 
        System.out.println("连接了5 6 之后的parent:");
        union.unionElements(5, 6);
        union.printArr(union.parent);
        System.out.println("连接了5 6 之后的weight:");
        union.printArr(union.weight);
 
        System.out.println("连接了1 2 之后的parent:");
        union.unionElements(1, 2);
        union.printArr(union.parent);
        System.out.println("连接了1 2 之后的weight:");
        union.printArr(union.weight);
 
        System.out.println("连接了2 3 之后的parent:");
        union.unionElements(2, 3);
        union.printArr(union.parent);
        System.out.println("连接了2 3 之后的weight:");
        union.printArr(union.weight);
 
        System.out.println("连接了1 4 之后的parent:");
        union.unionElements(1, 4);
        union.printArr(union.parent);
        System.out.println("连接了1 4 之后的weight:");
        union.printArr(union.weight);
 
        System.out.println("连接了1 5 之后的parent:");
        union.unionElements(1, 5);
        union.printArr(union.parent);
        System.out.println("连接了1 5 之后的weight:");
        union.printArr(union.weight);
 
        System.out.println("1  6 是否连接:" + union.isConnected(1, 6));
 
        System.out.println("1  8 是否连接:" + union.isConnected(1, 8));
    }
}

    使用height的情况

public class UnionFind {
    private int[] parent;
    private int[] height;
    int size;
 
    public UnionFind(int size) {
        this.size = size;
        this.parent = new int[size];
        this.height = new int[size];
        // 在初始化分组的同时也初始化height
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            height[i] = 1;
        }
    }
 
    public int find(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }
 
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
 
        if (height[firstRoot] < height[secondRoot]) {
            parent[firstRoot] = secondRoot;
        } else if (height[firstRoot] > height[secondRoot]) {
            parent[secondRoot] = firstRoot;
        } else {
            /*
              如果要合并的两个集合高度一样,那么随意选一个作为根
              我这里选的是让secondRoot作为新集合的根。
              然后secondRoot高度高了一层,所以+1
            */
            parent[firstRoot] = secondRoot;
            height[secondRoot] += 1;
        }
    }
 
    private void printArr(int[] arr){
        for(int p : arr){
            System.out.print(p+"\t");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);
 
        System.out.println("初始parent:");
        union.printArr(union.parent);
        System.out.println("初始height:");
        union.printArr(union.height);
 
        System.out.println("连接了5 6 之后的parent:");
        union.unionElements(5, 6);
        union.printArr(union.parent);
        System.out.println("连接了5 6 之后的height:");
        union.printArr(union.height);
 
        System.out.println("连接了1 2 之后的parent:");
        union.unionElements(1, 2);
        union.printArr(union.parent);
        System.out.println("连接了1 2 之后的height:");
        union.printArr(union.height);
 
        System.out.println("连接了2 3 之后的parent:");
        union.unionElements(2, 3);
        union.printArr(union.parent);
        System.out.println("连接了2 3 之后的height:");
        union.printArr(union.height);
 
        System.out.println("连接了1 4 之后的parent:");
        union.unionElements(1, 4);
        union.printArr(union.parent);
        System.out.println("连接了1 4 之后的height:");
        union.printArr(union.height);
 
        System.out.println("连接了1 5 之后的parent:");
        union.unionElements(1, 5);
        union.printArr(union.parent);
        System.out.println("连接了1 5 之后的height:");
        union.printArr(union.height);
 
        System.out.println("1  6 是否连接:" + union.isConnected(1, 6));
 
        System.out.println("1  8 是否连接:" + union.isConnected(1, 8));
    }
}

    下面略加修改代码,使之可以计算分组的数量,并对路径进行了两种优化

class UnionFind {
    private int[] parent;
    private int[] weight;
    private int size;//代表并查集中元素个数
    private int groups;//代表并查集中有多少个集合(小组)
 
    public UnionFind(int size) {
        this.parent = new int[size];
        this.weight = new int[size];
        this.size = size;
        // 初始化分组数量
        this.groups = size;//因为初始的时候每个人自成一组,所以有多少人就有多少组
        for (int i = 0; i < size; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }
 
    /* find第一种写法 */
    public int find(int element) {
        while (element != parent[element]) {
            // 路径对折,只压缩一层,改变从e 到根节点路径上每隔
            // 一个节点(除了根和其子节点)的指针,使其指向各自的祖父节点。
            parent[element] = parent[parent[element]];
            element = parent[element];
        }
        return element;
    }

    /* find第二种写法 
    public int find(int element) {
        int fa;
        while (element != parent[element]) {
            // 路径分割,只压缩一层,改变从e 到根节点路径上每个
            // 节点(除了根和其子节点)的指针,使其指向各自的祖父节点。
            fa = parent[element];
            parent[element] = parent[parent[element]];
            element = fa;
        }
        return element;
    }
    */
 
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
 
        //如果已经属于同一个集合了,就不用再合并了。
        if (firstRoot == secondRoot) {
            return;
        }
 
        if (weight[firstRoot] > weight[secondRoot]) {
            parent[secondRoot] = firstRoot;
            weight[firstRoot] += weight[secondRoot];
        } else {//weight[firstRoot] <= weight[secondRoot]
            parent[firstRoot] = secondRoot;
            weight[secondRoot] += weight[firstRoot];
        }
 
        //合并 firstElement 和 secondElement 所在的两个组后,就少了一组。
        this.groups--;
    }
 
    // 获取分组的数量
    public int getGroups() {
        return this.groups;
    }
}

    最后再说一下路径压缩,所谓路径压缩,是因为分组形成的树,高度不一定,分组内的元素要找到根结点,可能要进行若干次判断,所以我们想让所有的非根结点都直接与根结点相连,这样最多两次判断,就可以找到根结点,下面给出最终代码

public class UnionFind
{
	private int[] parent;
    private int[] weight;
    private int size;//代表并查集中元素个数
    private int groups;//代表并查集中有多少个集合(小组)
 
    public UnionFind(int size) {
        this.parent = new int[size];
        this.weight = new int[size];
        this.size = size;
        this.groups = size;//因为初始的时候每个人自成一组,所以有多少人就有多少组
        for (int i = 0; i < size; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }
 
    // 返回分组的根结点,一行代码
    public int find(int x) {
    	return x != parent[x] ? parent[x] = find(parent[x]) : parent[x];
    }
 
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
 
        //如果已经属于同一个集合了,就不用再合并了。
        if (firstRoot == secondRoot) {
            return;
        }
 
        if (weight[firstRoot] > weight[secondRoot]) {
            parent[secondRoot] = firstRoot;
            weight[firstRoot] += weight[secondRoot];
        } else {//weight[firstRoot] <= weight[secondRoot]
            parent[firstRoot] = secondRoot;
            weight[secondRoot] += weight[firstRoot];
        }
 
        //合并 firstElement 和 secondElement 所在的两个组后,就少了一组。
        this.groups--;
    }
 
    public int getGroups() {
        return this.groups;
    }
}

    注:一行代码搞定find和union函数

     int find(int x){
    	return x != parent[x] ? parent[x] = find(parent[x]) : parent[x];
    }
    
    void union(int x, int y){
        parent[find(y)] = find(x);
    }

 


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

2021-04-21 16:56
2021-04-17 02:06
2021-04-15 01:39
2021-04-04 07:16
2021-03-27 10:03
2021-03-01 11:50
2021-02-27 07:44
2021-02-24 14:02
2020-11-01 18:29
2020-11-01 15:27
广告位-帮帮忙点下广告