并查集(Java)

末蓝、 2023-07-04 04:51 6阅读 0赞

# 并查集 #

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。  
**并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林（多棵树）来表示。**

#### UF.java(并查集接口) ####

//并查集接口
    public interface UF {
        
    	int getSize();//返回并查集中树的个数，即集合的个数
    	boolean isConnected(int p,int q);//查询元素p与元素q是否连接
    	void unionElements(int p,int q);//将元素q与元素p进行合并
    }

#### UnionFind.java(并查集) ####

//并查集
    public class UnionFind implements UF {
        
    	private int[] parent;// 基础数组形成多棵树结构
    	// private int[] sz;// sz[i]表示以i为根的集合节点个数
    	private int[] rank;// rank[i]表示以i为根的集合所表示的树的层数(h)
    
    	public UnionFind(int size) {
        
    		// TODO Auto-generated constructor stub
    		parent = new int[size];
    		rank = new int[size];
    		for (int i = 0; i < size; i++) {
        
    			parent[i] = i;// 初始根节点
    			rank[i] = 1;// 初始每棵树的节点为1
    		}
    	}
    
    	@Override
    	public int getSize() {
        
    		// TODO Auto-generated method stub
    		return parent.length;
    	}
    
    	// 查找索引为p的根节点 路径压缩
    	// O(h)的复杂度 h为树的高度
    	private int find(int p) {
        
    		if (p < 0 && p >= parent.length)
    			try {
        
    				throw new Exception("p越界");
    			} catch (Exception e) {
        
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		// 非递归算法性能略微高于递归算法(递归算法需要有一定的内存开销)
    		while (p != parent[p]) {
        
    			parent[p] = parent[parent[p]];// 路径压缩 让当前p节点的父亲指向p节点父亲的父亲
    			p = parent[p];// 让p指向新的父亲节点
    		}
    		return p;
    		
    //		递归算法  路径压缩为深度最小
    //		if (p != parent[p])// 如果p不是根节点
    //			parent[p] = find(parent[p]);// p指向父亲节点的根节点 进行递归
    //		return parent[p];// 返回p的父亲节点即根节点
    	}
    
    	// 查看p元素与q元素是否属于一个集合
    	// O(h)的复杂度 h为树的高度
    	@Override
    	public boolean isConnected(int p, int q) {
        
    		// TODO Auto-generated method stub
    		return find(p) == find(q);
    	}
    
    	// 合并p元素与q元素所属的集合
    	// O(h)的复杂度 h为树的高度
    	@Override
    	public void unionElements(int p, int q) {
        
    		// TODO Auto-generated method stub
    		int proot = find(p);
    		int qroot = find(q);
    		if (proot == qroot)
    			return;
    		if (rank[proot] < rank[qroot]) {
        // p树的高度<q树的高度
    			parent[proot] = qroot;// p的根节点指向q的根节点
    		} else if (rank[proot] > rank[qroot]) {
         // p树的高度>q树的高度
    			parent[qroot] = proot;
    		} else p树的高度=q树的高度
    			parent[qroot] = proot;
    		rank[proot] += 1;// 高度相同时，合并后h+1
    	}
    
    }

#### 时间复杂度 ####

查询是否连接与合并方法的时间复杂度均为**O(h)**，h为所查询树的高度（深度）；  
如果是要讨论n的时间复杂度，即时间复杂度为**O(log\*n)**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200208120415685.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70