投稿
  1. 极客之音首页
  2. 后端开发
  3. Java

数据结构与算法–并查集

小半 • • Java • 阅读 80

导读：本篇文章讲解 数据结构与算法–并查集，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

数据结构–并查集

一. 并查集解决什么问题 ?

主要用于解决元素分组的问题,处理一些不相交集合,合并两个集合和查询两个集合是否连接

在这里插入图片描述

并查集的基本数据

  • 数组作为容器

  • 初始化时每个元素都是独立的一个集合,没有连接的元素

  • 当合并两个index(p,q)对应的元素时,将p的元素替换为q的元素或q的元素替换为p的元素

在这里插入图片描述

二.操作

写一个并查集的接口

package com.company.project.subject.day8;

public interface UnionFind {
    //获取元素个数
    int getSize();

    //合并
    void union(int p,int q);

    //判断是否连接  p,q 为元素所在数组的索引
    boolean isConnection(int p,int q);
}

在使用并查集时,并不关心元素内容,p,q分别为元素在数组中的索引

合并(两个集合)–void union(int p,int q)

查询(是否连接)–boolean isConnection(int p,int q)

​ 合并

在这里插入图片描述

并查集–数组

package com.company.project.subject.day8;

/**
 * 数组
 */
public class UF1 implements UnionFind {

    int[] ids;//元素所属的集合

    public UF1(int length) {
        ids = new int[length];
        //每个元素都是一个独立的集合
        for (int i = 0; i < ids.length; i++) {
            ids[i] = i;
        }
    }
    
    //辅助方法--根据元素在数组中的索引找所在集合的编号
    private int find(int index) {
        return ids[index];
    }

    @Override
    public int getSize() {
        return ids.length;
    }

    @Override
    public void union(int p, int q) {
        //定义两个不同的集合编号
        int pBoxNum = find(p);
        int qBoxNum = find(q);
        if(pBoxNum != qBoxNum){
            for (int i = 0; i < ids.length; i++) {
                if(find(i)==qBoxNum){
                    ids[i] = pBoxNum;
                }
            }
        }
    }

    @Override
    public boolean isConnection(int p, int q) {
        int pBoxNum = find(p);
        int qBoxNum = find(q);
        return pBoxNum == qBoxNum;
    }
    
    public static void main(String[] args) {
        UF1 uf1 = new UF1(10);
        uf1.ids = new int[]{1, 2, 3, 4,5};
        System.out.println(uf1.isConnection(0, 1));//false
        uf1.union(0, 1);//合并
        System.out.println(uf1.isConnection(0, 1));//true
    }
}

并查集–树

将每个元素看作是一个结点，结点之间相连接，形成树的结构

初始时,每个结点的顶层结点(根节点)是自身

例: 结点3与结点2相连接

在这里插入图片描述

将结点1与结点3相合并，只要将结点1指向结点3所在那棵树的根结点。

在这里插入图片描述

数据表示

union(4,3)

在这里插入图片描述

union(3,8)

在这里插入图片描述

union(6,5)–>union(9,4)–>union(2,1)–>union(5,0)–>union(7,2)–>union(6,2)

在这里插入图片描述

并查集1.0

package com.company.project.subject.day8;

public class UF2 implements UnionFind{
    private int[] parents;//顶层结点

    
    public UF2(int length){
        parents = new int[length];
        //每个元素对应一棵树,每棵树的顶层结点指向自身
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }
    }

    //辅助方法--根据元素在数组中的索引找所在集合的编号
    private int find(int index) {
        //index == parents[index]  索引的父节点是自己-->即是顶层结点
        while (index!=parents[index]){
            index = parents[index];//将父亲结点作为索引
        }
        return index;
    }

    @Override
    public int getSize() {
        return parents.length;
    }

    @Override
    public void union(int p, int q) {
        int pBoxNum = find(p);
        int qBoxNum = find(q);
        if(pBoxNum != qBoxNum){
            parents[pBoxNum] = qBoxNum;
        }
    }

    //两个索引对应结点所在的那棵树的顶层结点相同时,认为是连接的
    @Override
    public boolean isConnection(int p, int q) {
        int pBoxNum = find(p);
        int qBoxNum = find(q);
        return pBoxNum == qBoxNum;
    }
}

测试性能

写一个静态方法

public static void test(UnionFind uf, int count) {
        long startTime = System.nanoTime();
        int size = uf.getSize();
        Random random = new Random();
        for (int i = 0; i < count; i++) {
            int p = random.nextInt(size);
            int q = random.nextInt(size);
            uf.union(p, q);
        }
        for (int i = 0; i < count; i++) {
            int p = random.nextInt(size);
            int q = random.nextInt(size);
            uf.isConnection(p, q);
        }
        long endTime = System.nanoTime();
        System.out.println("Times:" + (endTime - startTime) / 1000000000.0);
    }

测试

size=100000;count=10000;

 		int size = 100000;
        int count = 10000;
        UF1 uf1 = new UF1(size);        //Times:0.5463024
        test(uf1, count);
        UF2 uf2 = new UF2(size);        //Times:0.0025296
        test(uf2, count);

size=100000;count=100000;

		int size = 100000;
        int count = 100000;
        UF1 uf1 = new UF1(size);        //Times:7.1844275
        test(uf1, count);
        UF2 uf2 = new UF2(size);        //Times:11.5945761
        test(uf2, count);

当循环次数越大时,树形结构的并查集比数组更耗时树形结构并查集复杂度为O(h):h为树的深度

在最坏情况下,深度非常大

在这里插入图片描述

并查集2.0–基于size的优化(降低树的深度)

思想:将元素个数较少的树合并到元素个数多的树上,从而降低深度

需要定义一个size数组,存储每棵树的元素个数

package com.company.project.subject.day8;

/**
 * 对size优化 合并时将结点少的树挂到结点多的顶层结点上面去,减小树的高度
 */
public class UF3 implements UnionFind{
    private int[] parents;//父结点
    private int[] size;//每颗树的结点个数

    public UF3(int length){
        parents = new int[length];
        size = new int[length];
        //每个元素对应一棵树,每棵树的顶层结点指向自身
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
            size[i] = i;
        }
    }

    //辅助方法--根据元素在数组中的索引找所在集合的编号
    private int find(int index) {
        //index == parents[index]  索引的父节点是自己-->即是顶层结点
        while (index!=parents[index]){
            index = parents[index];//将父亲结点作为索引
        }
        return index;
    }
    
    @Override
    public int getSize() {
        return parents.length;
    }

    @Override
    public void union(int p, int q) {
        int pBoxNum = find(p);
        int qBoxNum = find(q);
        if(pBoxNum != qBoxNum){
            if(size[pBoxNum] < size[qBoxNum]){
                //如果p的结点个数 < q 将p的父节点指向q
                parents[pBoxNum] = qBoxNum;
                //更新合并后的结点个数  将结点少的挂到结点多的上
                size[qBoxNum] += size[pBoxNum];
            }else{
                parents[qBoxNum] = pBoxNum;
                size[pBoxNum] += size[qBoxNum];
            }
        }
    }
	
    //两个索引对应结点所在的那棵树的顶层结点相同时,认为是连接的
    @Override
    public boolean isConnection(int p, int q) {
        int pBoxNum = find(p);
        int qBoxNum = find(q);
        return pBoxNum == qBoxNum;
    }
}

size优化的缺点

在这里插入图片描述

在这里插入图片描述

并查集3.0–基于高度进行优化

package com.company.project.subject.day8;

/**
 * size 优化有缺点
 * 对 高度 进行优化 合并时将深度低的树挂到深度高的顶层结点上去,减小树的深度
 */
public class UF4 implements UnionFind{
    private int[] parents;//父结点
    private int[] rank;//树的高度

    public UF4(int length){
        parents = new int[length];
        rank = new int[length];
        //每个元素对应一棵树,每棵树的顶层结点指向自身
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
            rank[i] = i;//初始高度都为1,只有一个元素
        }
    }
	
    //辅助方法--根据元素在数组中的索引找所在集合的编号
    private int find(int index) {
        //index == parents[index]  索引的父节点是自己-->即是顶层结点
        while (index!=parents[index]){
            index = parents[index];//将父亲结点作为索引
        }
        return index;
    }

    @Override
    public int getSize() {
        return parents.length;
    }

    @Override
    public void union(int p, int q) {
        int pBoxNum = find(p);
        int qBoxNum = find(q);
        if(pBoxNum != qBoxNum){
            if(rank[pBoxNum] < rank[qBoxNum]){
                //如果p的结点个数 < q 将p的父节点指向q
                parents[pBoxNum] = qBoxNum;
            }else if(rank[qBoxNum] < rank[pBoxNum]){
                parents[qBoxNum] = pBoxNum;
            }else{//高度相等时,可以互相挂,高度+1
                parents[pBoxNum] = qBoxNum;
                rank[qBoxNum] += 1;
            }
        }
    }

    //两个索引对应结点所在的那棵树的顶层结点相同时,认为是连接的
    @Override
    public boolean isConnection(int p, int q) {
        int pBoxNum = find(p);
        int qBoxNum = find(q);
        return pBoxNum == qBoxNum;
    }
}

并查集4.0–路径压缩

  • 方法：parent[p]= parent[parent[p]]
  • 路径压缩发生的时机：find()

在这里插入图片描述

	//find操作改变了
	private int find(int index) {
        //index == parents[index]  索引的父节点是自己-->即是顶层结点
        while (index!=parents[index]){
            //当前结点指向父节点的父节点
            parents[index] = parents[parents[index]];
            index = parents[index];//将父亲结点作为索引
        }
        return index;
    }

	//合并操作不变
	@Override
    public void union(int p, int q) {
        int pBoxNum = find(p);
        int qBoxNum = find(q);
        if(pBoxNum != qBoxNum) {
            parents[pBoxNum] = qBoxNum;
        }
    }

并查集5.0–路径压缩优化

在这里插入图片描述

find操作

	private int find(int index) {
        //index == parents[index]  索引的父节点是自己-->即是顶层结点
        if (index!=parents[index]){
            parents[index] = find(parents[index]);
        }
        return parents[index];
    }

在这里插入图片描述

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/15609.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！