简单实现并查集(基于数组和基于树)

逃离我推掉我的手 2022-02-21 08:24 37阅读 0赞

# 并查集: #

> 并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。(来自百度百科)

关于并查集的实现,有两种思路.  
**一种是基于数组** ,这种思路是将每个元素所属的集合编号存在数组中,然后随着集合编号的合并和,修改数组的编号即可,代码实现如下

首先定义一个并查集的接口:

/** * @author BestQiang */
    public interface UF { 
        int getSize();
        boolean isConnected(int p, int q);
        void unionELements(int p, int q);
    }

接下来实现并查集接口:

/** * @author BestQiang */
    public class UnionFind1 implements UF { 
    
        private int[] id;
    
        public UnionFind1(int size) { 
            // 初始化并查集,此时所有元素属于不同的集合
            this.id = new int[size];
            for (int i = 0; i < id.length; i++) { 
                id[i] = i;
            }
        }
    
        @Override
        public int getSize() { 
            return 0;
        }
    
        /** * 查找元素p所对应的的集合编号 * @param p * @return */
        private int find(int p) { 
            if(p < 0 && p >= id.length) { 
                throw new IllegalArgumentException("p is out of bound.");
            }
            // 直接返回对应的集合编号即可
            return id[p];
        }
    
        /** * 查看元素p和元素q是否所属一个集合 * @param p * @param q * @return */
        @Override
        public boolean isConnected(int p, int q) { 
            return find(p) == find(q);
        }
    
        /** * 合并元素p和元素q所属的集合 * @param p * @param q */
        @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;
                }
            }
        }
    
    }

**另一种是基于树** ,这种树不是一般的树,这种树是由下层节点指向上层节点的树,基于数组实现,如图所示:  
![在这里插入图片描述][20190410171110502.png]  
将数组的值储存为父节点的id即可,代码实现如下:

/** * @author BestQiang */
    public class UnionFind2 implements UF{ 
        private int[] parent;
        public UnionFind2(int size) { 
            parent = new int[size];
            for(int i = 0; i < size; i++) { 
                parent[i] = i;
            }
        }
    
        @Override
        public int getSize() { 
            return parent.length;
        }
    
        /** * 查找过程,查找元素p所对应的集合编号 * O(h)复杂度,h为树的高度 * @param p * @return */
        private int find(int p) { 
            if(p < 0 && p >= parent.length) { 
                throw new IllegalArgumentException("p is out of bound");
            }
    
            // 循环查找p的根节点(原理是查找p的上层节点,找到后将上层节点赋值给p,继续找上层节点,相同才截止)
            while (p != parent[p]) { 
                p = parent[p];
            }
            return p;
        }
    
        /** * 查看元素p和元素q是否所属一个集合 * O(h)复杂度, h为树的高度 * @param p * @param q * @return */
        @Override
        public boolean isConnected(int p, int q) { 
            // 如果根节点相同,直接判定为所属一个集合
            return find(p) == find(q);
        }
    
        /** * 合并两个节点 * @param p * @param q */
        @Override
        public void unionELements(int p, int q) { 
            int pRoot = find(p);
            int qRoot = find(q);
    
            // 根节点相同,代表已经所属同组,直接结束即可
            if(pRoot == qRoot) { 
                return;
            }
    
            // 根节点不同,就将pRoot的上层设置到q的根节点即可
            // 为什么要直接连接到qRoot的根节点,不直接连接到qRoot的上层节点?目的是发挥树的特性,便于查询
            parent[pRoot] = qRoot;
        }
    }

[20190410171110502.png]: /images/20220221/e8f8501c93ee49098ad0b8d54f466e9f.png