自定义并查集

一种特殊的多叉树。

主要支持两个方法：①union(p,q)  ②isConnected(p,q)

 

 

find方法中的路径压缩：

 

 

 

基于rank的优化：

 

 

          以 union(4,2)为例： 将层数最少的元素2的根节点，指向层数较多的元素4的根节点。

                            首先是这样的

                                                最终结果为

 

 

 

并查集的时间复杂度为：O(h)   h代表树的深度：

 

  总之 ，其时间复杂度近乎为O(1).

 

 

包结构：

 

UF.java接口：

package UnionFind;

public interface UF {
	//并查集中元素的个数
	int getSize();
	//判断元素p和元素q是否属于同一集合
	boolean isConnected(int p,int q);
	//合并元素p所在的集合与元素q所在的集合
	void unionElements(int p,int q);
}

 

UnionFind.java:

package UnionFind;

public class UnionFind implements UF{
	//rank[i]表示以i为根的集合所表示的树的层数
    // 只是作为比较的一个标准,并没有不断维护。所以rank的值在路径压缩的过程中, 有可能不再是树的层数值
	private int[] rank;
	
	private int[] parent;// parent[i]表示第i个元素所指向的父节点
	/**
	 * 构造函数
	 * @param size
	 */
	public UnionFind(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;
	}
	
	/**
	 * 辅助方法
	 * 查找过程, 查找元素p所对应的集合编号
	 * @param p
	 * @return
	 */
	private int find(int p) {
		if(p < 0 || p >= parent.length)
            throw new IllegalArgumentException("索引越界");

        // 不断去查询自己的父亲节点, 直到到达根节点
        // 路径压缩，递归算法
        while(p != parent[p])
            parent[p]=find(parent[p]);
        return parent[p];
	}
	/**
	 * 判断元素p和元素q是否属于同一集合
	 */
	@Override
	public boolean isConnected(int p, int q) {
		
		return find(p)==find(q);
	}
	/**
	 * 合并元素p所在的集合与元素q所在的集合
	 */
	@Override
	public void unionElements(int p, int q) {
		 int pRoot = find(p);
	        int qRoot = find(q);

	        if( pRoot == qRoot )
	            return;

	        // 根据两个元素所在树的rank不同判断合并方向
	        // 将rank低的集合合并到rank高的集合上
	        if( rank[pRoot] < rank[qRoot] )
	            parent[pRoot] = qRoot;
	        else if( rank[qRoot] < rank[pRoot])
	            parent[qRoot] = pRoot;
	        else{ // rank[pRoot] == rank[qRoot]
	            parent[pRoot] = qRoot;
	            rank[qRoot] += 1;   // 维护rank的值
	        }
		
	}
	

}