并查集

並查集森林

並查集森林是一種將每一個集合以樹表示的資料結構，其中每一個節點儲存著到它的父節點的參照（見義大利麵條堆疊）。這個資料結構最早由Bernard A. Galler和Michael J. Fischer於1964年提出，但是經過了數年才完成了精確的分析。
在並查集森林中，每個集合的代表即是集合的根節點。「尋找」根據其父節點的參照向根行進直到到底樹根。「聯合」將兩棵樹合併到一起，這通過將一棵樹的根連接到另一棵樹的根。實現這樣操作的一種方法是
 function MakeSet(x)
     x.parent := x
 function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot
這是並查集森林的最基礎的表示方法，這個方法不會比連結串列法好，這是因為建立的樹可能會嚴重不平衡；然而，可以用兩種辦法最佳化。
第一種方法，稱為「按秩合併」，即總是將更小的樹連接至更大的樹上。因為影響執行時間的是樹的深度，更小的樹添加到更深的樹的根上將不會增加秩除非它們的秩相同。在這個演算法中，術語「秩」替代了「深度」，因為同時應用了路徑壓縮時（見下文）秩將不會與高度相同。單元素的樹的秩定義為，當兩棵秩同為的樹聯合時，它們的秩。只使用這個方法將使最壞的執行時間提高至每個MakeSet、Union或Find操作。最佳化後的MakeSet和Union虛擬碼：
 function MakeSet(x)
     x.parent := x
     x.rank   := 0
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot == yRoot
         return

     // x和y不在同一个集合，合并它们。
     if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1
第二個最佳化，稱為「路徑壓縮」，是一種在執行「尋找」時扁平化樹結構的方法。關鍵在於在路徑上的每個節點都可以直接連接到根上；他們都有同樣的表示方法。為了達到這樣的效果，Find遞迴地經過樹，改變每一個節點的參照到根節點。得到的樹將更加扁平，為以後直接或者間接參照節點的操作加速。這兒是Find：
 function Find(x)
     if x.parent != x
        x.parent := Find(x.parent)
     return x.parent
這兩種方法的優勢互補，同時使用二者的程式每個操作的平均時間僅為，是的反函式，其中是急速增加的阿克曼函式。因為是其的反函式，故在十分巨大時還是小於5。因此，平均執行時間是一個極小的常數。
實際上，這是漸近最佳演算法：Fredman和Saks在1989年解釋了的平均時間內可以獲得任何並查集。

主要操作

需要注意的是，一開始我們假設元素都是分別屬於一個獨立的集合里的。

合併兩個不相交集合

操作很簡單：先設定一個陣列(陣列)Father[x]，表示x的「父親」的編號。
那麼，合併兩個不相交集合的方法就是，找到其中一個集合最父親的父親（也就是最久遠的祖先），將另外一個集合的最久遠的祖先的父親指向它。
Pascal程式碼：
procedure Union(x,y:integer);{其中GetFather是下面将讲到的操作}
 var fx,fy : integer;
  begin
     fx := getfather(x);
     fy := getfather(y);
     If fx<>fy then father[fx] := fy;{指向最祖先的祖先}
  end;
C語言代碼表示形式:
void Union(int x,int y){
    fx = getfather(x);
    fy = getfather(y);
    if(fy!=fx)
       father[fx]=fy;}

判斷兩個元素是否屬於同一集合

仍然使用上面的陣列。則本操作即可轉換為尋找兩個元素的最久遠祖先是否相同。尋找祖先可以採用遞迴實現，見後面的路徑壓縮演算法。
Pascal程式碼：
Function Same(x,y:integer):boolean;begin
  Same:=GetFather(x)=GetFather(y);end;
C程式碼：
bool same(int x,int y){
   return getfather(x)==getfather(y);}/*返回true 表示相同根结点，返回false不相同*/

路徑壓縮

剛才我們說過，尋找祖先時採用遞迴，但是一旦元素一多起來，或退化成一條鏈，每次GetFather都將會使用的複雜度，這顯然不是我們想要的。
對此，我們必須要進行路徑壓縮，即我們找到最久遠的祖先時「順便」把它的子孫直接連接到它上面。這就是路徑壓縮了。使用路徑壓縮的程式碼如下：
Pascal 語言的實現：
Function getfather(v:integer):integer;
  begin
    if (father[v]=v) then
      getfather:=v
    else
      begin
        father[v]:=getfather(father[v]);{路径压缩}
        getfather:=father[v];
      end;
  end;
C 語言的實現：
int getfather(int v){
    if (father[v]==v)
      return v;
    else
    {
        father[v]=getfather(father[v]);//路径压缩
        return father[v];
     }}

Rank合併

合併時將元素所在深度小的集合合併到元素所在深度大的集合。
Pascal 語言的實現：
function judge(x,y:integer):boolean;
 var fx,fy : integer;
  begin
     fx := getfather(x);
     fy := getfather(y);
     If fx=fy then 
       exit(true)
     else 
       judge := false;
     if rank[fx]>rank[fy] then
       father[fy] := fx
     else begin
       father[fx] := fy;
       if rank[fx]=rank[fy] then 
         inc(rank[fy]);
     end;
  end;
初始化：
fillchar(rank,sizeof(rank),0);
C 語言的實現：
void judge(int x ,int y){
     fx = getfather(x);
     fy = getfather(y);

     if (rank[fx]>rank[fy])
        father[fy] = fx;
     else
     {
        father[fx] = fy;
        if(rank[fx]==rank[fy])
           ++rank[fy]; //重要的是祖先的rank，所以只用修改祖先的rank就可以了，子节点的rank不用管
     }}
初始化：
memset(rank,0,sizeof(rank));

時間複雜度

同時使用路徑壓縮、按秩（rank）合併最佳化的程式每個操作的平均時間僅為 ，其中  是  的反函式， 是急速增加的阿克曼函式。因為  是其反函式，故  在  十分巨大時還是小於。因此，平均執行時間是一個極小的常數。實際上，這是漸近最佳演算法：Fredman 和 Saks 在 1989 年解釋了  的平均時間內可以獲得任何並查集。

空間複雜度

（為元素數量）