不相交集合（並查集）
不相交集合（兩集合中沒有相交元素），因為只能 進行合並和查找所求元素所在的集合，因此被稱為並查集，至於怎麼標志哪一個集合，可以使用集合的頭結點（使用鏈表表示並查集），若果返回的元素一樣則表示為同一個集合。如果使用森林表示，則用根節點代表這一個集合。只連接兩個根節點即可。
這一般應用 在無向圖的連通分量和一些圖的算法中。
下面說明兩種實現方式：
1. 不相交森林（數組實現）
森林不需要記錄屬於那個幾個的指針，只合並根節點，在合並根節點時使用啟發試的策略是按秩合並和路徑壓縮。
這裡的秩為根節點的深度。秩小的根節點作為秩大的孩子，一個根節點可有很多孩子，是一個森林。
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjwvcD4KPHA+PHByZSBjbGFzcz0="brush:java;">package Algorithms;
/**
* 不相交集合森林 使用數組實現，單純的使用父親指針實現不了
* 森林，不能找到所表示的節點，而數組可以使用下標。
*但是可以使用鏈表實現。節點只有next指針，
* @param
*/
public class DisjointSet {
//不相交集合的節點定義
private static class Node
{
public T key;
public int rank;
public int p;
public Node(T key,int rank,int p){
this.key=key;
this.rank=rank;
this.p=p;
}
}
private Node s[];//次數組存放的元素 並不一定是一個集合中
private int size;//數組元素的個數
public DisjointSet(int eleNum){
size=0;
s=new Node[eleNum];
}
/**
* 構造一個只含有集合，只有一個元素，存放於s中
*/
public void makeSet(int x,T key)
{
size++;
s[x]=new Node(key,0,x);
}
/** 合並兩個元素所在的集合
* （利用深度合並 深度小的合並到大的上，根節點深度不變，若兩個跟秩一樣
* 深度要加1）
* @param x
* @param y
*/
public void union(int x,int y){
x=findSet(x);
y=findSet(y);
if(s[x].rank>s[y].rank)
s[y].p=x;
else
{
s[x].p=y;
if(s[x].rank==s[y].rank)
s[x].rank++;
}
}
/**
* 路徑壓縮的findSet（發現集合 的代表元素 這裡為根節點）
* 查找的時間復雜度與深度有關 ，所以不相交集合結構為森林結構，一個節點可以
* 有多個孩子
*/
public int findSet(int x)
{
if(s[x].p==x)
return x;
else
return findSet(s[x].p);
}
public static void main(String args[])
{
DisjointSetds=new DisjointSet(2);
ds.makeSet(0, 0);
ds.makeSet(1, 1);
ds.union(0, 1);
}
}
2.不相交集合的鏈表實現
因為此實現比較簡單，所以這裡只是說明每個節點的結構體：
struct Node{
Node * next；//此節點的下一個元素
Node * set；//此節點屬於的集合 一般指向head指針
T key；//元素關鍵字
}
struct Disjoint{
Node *head;
Node* tail;
int rank；//每個集合的權值
}
當使用鏈表實現，合並以後需要改變每個節點的指向的集合，所以為了減少時間復雜度，采用加權合並的啟發試策略，這裡的權為元素個數，權值小的合並到權值大的鏈表上。顯然不如森林的效果好。
