java实现数据结构11（并查集详解代码之自定义并查集）

小鱼儿 2023-06-23 13:29 29阅读 0赞

## 并查集接口 ##

/** * @description: 自定义并查集接口 * @author: liangrui * @create: 2019-12-19 13:22 **/
    public interface UnionFind { 
    
        /** * 获取元素个数 * @return */
        int getSize();
    
        /** * 连接元素 * @param p * @param q */
        void unionElements(int p,int q);
    
        /** * 判断两个元素是否关联 * @param p * @param q * @return */
        boolean isConnected(int p,int q);
    }

## 基于数组自定义普通并查集 ##

/** * @description: 并查集,基于数组，不是树结构 * @author: liangrui * @create: 2019-12-19 15:43 **/
    public class UF1 implements UnionFind{ 
    
        private int[] id;
    
        public UF1(int size){ 
            id=new int[size];
    
            //初始化，每一个id[i]指向自己，没有合并的元素
            for (int i = 0; i < size; i++) { 
                id[i]=i;
            }
        }
    
        @Override
        public int getSize() { 
            return id.length;
        }
    
        /** * 查询元素e所对应的集合编号，复杂度：O(1) * @param e * @return */
        private int find(int e){ 
            if (e<0||e>=id.length){ 
                throw new IllegalArgumentException("e is out of bound");
            }
            return id[e];
        }
    
    
        @Override
        public void unionElements(int p, int q) { 
            int pId=find(p);
            int qId=find(q);
    
            if (pId==qId){ 
                return;
            }
    
            //合并过程需要遍历所有元素，将两个元素的所属集合编号合并
            for (int i = 0; i < id.length; i++) { 
                if (id[i]==pId){ 
                    id[i]=qId;
                }
            }
        }
    
        /** * 查看元素p和元素q是否属于一个集合，复杂度：O(1) * @param p * @param q * @return */
        @Override
        public boolean isConnected(int p, int q) { 
            return find(p)==find(q);
        }
    }

## 基于数组自定义优化的高效率并查集 ##

/** * @description: 并查集，基于数组，是树结构,效率很高 * @author: liangrui * @create: 2019-12-19 16:14 **/
    public class UF2 implements UnionFind { 
    
        //使用一个数组构建一棵指向父节点的树
        private int[] parent;
        //rank[i]表示以i为根的集合的层数
        private int[] rank;
    
        public UF2(int size){ 
            parent=new int[size];
            rank=new int[size];
    
            //初始化，每一个parent[i]指向自己，表示每一个元素自己自成一个集合
            for (int i = 0; i < size; i++) { 
                parent[i]=i;
                rank[i]=1;
            }
        }
    
        @Override
        public int getSize() { 
            return parent.length;
        }
    
        /** * 查找元素e所对应的集合编号，复杂度：O(h),h为树的高度 * @param e * @return */
        private int find(int e){ 
            if (e<0||e>=parent.length){ 
                throw new IllegalArgumentException("e is out of bound.");
            }
    
            if(e!=parent[e]){ 
                //路径压缩，提高效率，不需要维护集合层数，因为不影响集合的合并，而且如果维护层数，反而使效率降低
                parent[e]=parent[parent[e]];
                e=parent[e];
            }
            return e;
        }
    
        /** *合并元素p和元素q所属的集合，复杂度：O(h),h为树的高度 * @param p * @param q */
        @Override
        public void unionElements(int p, int q) { 
            int pRoot=find(p);
            int qRoot=find(q);
    
            if (pRoot==qRoot){ 
                return;
            }
    
            //将层数少的集合合并到层数多的集合上
            if (rank[pRoot]<rank[qRoot]){ 
                parent[pRoot]=qRoot;
            }else if(rank[pRoot]>rank[qRoot]) { 
                parent[qRoot]=pRoot;
            }else { 
                parent[qRoot]=pRoot;
                rank[pRoot]++;
            }
    
        }
    
        /** *查看元素p和q是否属于一个集合，复杂度：O(h),h为树的高度 * @param p * @param q * @return */
        @Override
        public boolean isConnected(int p, int q) { 
            return find(p)==find(q);
        }
    }

## main测试比较两个并查集的执行效率 ##

import java.util.Random;
    
    public class Main { 
    
        /** * 测试执行时间，单位：秒 * @param uf 并查集 * @param num 执行次数 * @return 返回执行时间 */
        private static double testUF(UnionFind uf,int num){ 
            int size=uf.getSize();
            Random random=new Random();
    
            long beginTime = System.nanoTime();
    
            for (int i = 0; i < num; i++) { 
                int a=random.nextInt(size);
                int b=random.nextInt(size);
                uf.unionElements(a,b);
            }
    
            for (int i = 0; i < num; i++) { 
                int a=random.nextInt(size);
                int b=random.nextInt(size);
                uf.isConnected(a,b);
            }
    
            long endTime = System.nanoTime();
    
            return (endTime-beginTime)/1000000000.0;
        }
    
        public static void main(String[] args) { 
            //并查集初始集合个数
            int size=1000000;
            //执行次数
            int num=1000000;
    
            UF1 uf1=new UF1(size);
            System.out.println("UF1:"+testUF(uf1,num)+"s");
    
            UF2 uf2=new UF2(size);
            System.out.println("UF2:"+testUF(uf2,num)+"s");
    
        }
    }

## 执行结果： ##

> UF1:570.5369963s  
> UF2:0.2014325s