并查集

落日映苍穹つ 2022-06-16 12:44 286阅读 0赞

# 并查集JAVA版框架 #

##     ##

## 并查集是一种用来管理元素分组情况的数据结构。 ##

## 并查集可以高效地进行如下操作： ##

\--查询元素a和元素b是否属于同一组

\--合并元素a和元素b所在的组

**不过需要注意的是：并查集虽然可以进行合并操作，却不可以进行分割操作。**

**在树形结构里，如果发生了退化的情况，复杂度就会变得很高，因此有必要避免退化的发生，按照如下的操作，就可以避免退化：**

\--对于每棵树，记录这棵树的高度。

\--合并时，如果两棵树的rank不同，那么从rank小的向rank大的连接边，即rank小的树作为rank大的树的子树。

此外，通过路径压缩，可以使得并查集更加高效，对于每个节点，一旦向上走到了一次根节点，就把这个点到父亲的边改为直接连向根。

在此之上，在查询过程中，向上经过的所有节点，都改为直接连接到跟上，这样再次查询这些节点时，就可以很快知道根是谁了。

**并查集的复杂度**

对n个元素的并查集进行一次操作的复杂度是O(a(n))，这里的a(n)是阿克曼函数的反函数，这比O(log(n))还要快，不过这是“均摊复杂度”，即并不是每一次操作都满足这个复杂度，二是多次操作后平均每一次操作的复杂度是O(a(n))的意思。

## 下面是并查集实现的JAVA代码    ##

package tree;
    
    public class UnionFindSet {
    
    	/**
    	 * 祖先节点
    	 */
    	private int [] par;
    	
    	/**
    	 * 树的高度
    	 * 用来避免树的退化带来的复杂度上升
    	 */
    	private int [] rank;
    	
    	/**
    	 * 初始化n个元素
    	 * @param n
    	 */
    	public void init(int n){
    		for(int i=0;i<n;++i){
    			par[i]=i;
    			rank[i]=0;
    		}
    	}
    	
    	/**
    	 * 查询树的根
    	 * @param x
    	 * @return
    	 */
    	public int find(int x){
    		if(par[x]==x){
    			return x;
    		}
    		else{
    			return par[x]=find(par[x]);
    		}
    	}
    	
    	/**
    	 * 合并x和y所属的集合
    	 */
    	public void unite(int x,int y){
    		x=find(x);
    		y=find(y);
    		if(x==y){
    			return ;
    		}
    		if(rank[x]<rank[y]){
    			par[x]=y;
    		}
    		else{
    			par[y]=x;
    			if(rank[x]==rank[y]){
    				rank[x]++;
    			}
    		}
    	}
    	
    	/**
    	 * 判断x和y是否属于同一个集合
    	 * @param x
    	 * @param y
    	 * @return
    	 */
    	public boolean same(int x,int y){
    		return find(x)==find(y);
    	}
    	
    	
    }