java 資料結構並查集詳解

public abstract class UnionFind {
 
	 int[] parents;
	/**
	 * 初始化並查集
	 * @param capacity
	 */
	public UnionFind(int capacity){
		
		if(capacity < 0) {
			throw new IllegalArgumentException("capacity must be >=0");
		}
        //初始時每一個元素父節點（根結點）是自己
		parents = new int[capacity];
		for(int i = 0; i < parents.length;i++) {
			parents[i] = i;
		}
	}
	
   /**
     *  檢查v1 v2 是否屬於同一個集合
     */
	public boolean isSame(int v1,int v2) {
		return find(v1) == find(v2);
	}
 
    /**
     *  查詢v所屬的集合 （根節點）
     */
	public  abstract int find(int v);
 
	/**
     *  合併v1 v2 所屬的集合
     */
	public abstract void union(int v1, int v2);
	
		
	// 範圍檢查
	public   void rangeCheck(int v)  {
		if(v<0 || v > parents.length)
			throw new IllegalArgumentException("v is out of capacity");
	}
}

public class UnionFind_QF extends UnionFind {
	public UnionFind_QF(int capacity) {
		super(capacity);
		
	}
 
  // 查
@Override
	public  int  find(int v) {
		rangeCheck(v);
		return parents[v];
	}
 
 // 並 將v1所在集合併到v2所在集合上
@Override
public void union(int v1, int v2) {
    // 查詢v1 v2 的父（根）節點
	int p1= find(v1);
	int p2 = find(v2);
	if(p1 == p2) return;
  
    //將所有以v1的根節點為根節點的元素全部併到v2所在集合上 即父節點改為v2的父節點
	for(int i = 0; i< parents.length; i++) {
		if(parents[i] == p1) {
			parents[i] = p2;
		}
	}
	
  }
}

public class UnionFind_QU extends UnionFind {
 
	public UnionFind_QU(int capacity) {
		super(capacity);
		
	}
 
	//查某一個元素的根節點
	@Override
	public int find(int v) {
   //檢查下標是否越界
		rangeCheck(v);
   
  // 一直迴圈查詢節點的根節點
		while (v != parents[v]) {
			v = parents[v];
		}
		return v;
	}
 
//V1 併到 v2 中
	@Override
	public void union(int v1, int v2) {
	
		int p1 = find(v1);
		int p2 = find(v2);
		if(p1 == p2) return;
      //將v1 根節點 的 父節點 修改為 v2的根結點 完成合並
		parents[p1] = p2;
	}
}

public class UniondFind_QU_S extends UnionFind{
 
   // 建立sizes 陣列記錄 以元素（下標）為根結點的元素（節點）個數
	private int[] sizes;
 
	public UniondFind_QU_S(int capacity) {
		super(capacity);
 
		sizes = new int[capacity];
 
   //初始都為 1
		for(int i = 0;i < sizes.length;i++) {
			sizes[i] = 1;
			}
		
	}
 
	@Override
	public int find(int v) {
 
		rangeCheck(v);
 
		while (v != parents[v]) {
			v = parents[v];
		}
		return v;
	}
 
	@Override
	public void union(int v1, int v2) {
	
		int p1 = find(v1);
		int p2 = find(v2);
		if(p1 == p2) return;
 
		//如果以p1為根結點的元素個數 小於 以p2為根結點的元素個數 p1併到p2上，並且更新p2為根結點的元素個數
	if(sizes[p1] < sizes[p2]) {
		    parents[p1] = p2;
		    sizes[p2] += sizes[p1];
		
 // 反之 則p2 併到 p1 上，更新p1為根結點的元素個數
	}else {
			parents[p2] = p1;
			sizes[p1] += sizes[p2];
		}
	}
}

public class UnionFind_QU_R extends UnionFind_QU {
   // 建立rank陣列  ranks[i] 代表以i為根節點的樹的高度
 private int[] ranks;
 
	public UnionFind_QU_R(int capacity) {
		super(capacity);
 
		ranks = new int[capacity];
 
		for(int i = 0;i < ranks.length;i++) {
			ranks[i] = 1;
		}
 
	}
    
	public void union(int v1, int v2) {
 
		int p1 = find(v1);
		int p2 = find(v2);
		if(p1 == p2) return;
    
    // p1 併到 p2 上 p2為根 樹的高度不變
		if(ranks[p1] < ranks[p2]) {
			parents[p1] = p2;
			
  // p2 併到 p1 上 p1為根 樹的高度不變
		} else if(ranks[p1] > ranks[p2]) {
			parents[p2] = p1;
 
		}else {
    // 高度相同 p1 併到 p2上，p2為根 樹的高度+1
			parents[p1] = p2;
			ranks[p2] += 1;
		}
	}
}

/**
 *  Quick Union -基於rank的優化  -路徑壓縮
 *
 */
public class UnionFind_QU_R_PC extends UnionFind_QU_R {
 
	public UnionFind_QU_R_PC(int capacity) {
		super(capacity);
		
	}
 
	@Override
	public int find(int v) {
		rangeCheck(v);
 
		if(parents[v] != v) {
 
        //遞迴 使得從當前v 到根節點 之間的 所有節點的 父節點都改為根節點
			parents[v] = find(parents[v]);
		}
		return parents[v];
	}
}

/**
 *  Quick Union -基於rank的優化  -路徑分裂
 *
 */
public class UnionFind_QU_R_PS extends UnionFind_QU_R {
 
	public UnionFind_QU_R_PS(int capacity) {
		super(capacity);
		
	}
 
	@Override
	public int find(int v) {
		rangeCheck(v);
		while(v != parents[v]) {
 
			int p = parents[v];
			parents[v] = parents[parents[v]];
			v = p;
		}
		return v;
	}
}

/**
 *  Quick Union -基於rank的優化  -路徑減半
 *
 */
public class UnionFind_QU_R_PH extends UnionFind_QU_R {
 
	public UnionFind_QU_R_PH(int capacity) {
		super(capacity);
		
	}
	
	
    public int find(int v) {
    	rangeCheck(v);
 
		while(v != parents[v]) {
			parents[v] = parents[parents[v]];
			v = parents[v];
		}
		return v;
	}	 
 }