併查集

在計算機科學中，併查集（英文：Disjoint-set data structure，直譯為不交集數據結構）是一種數據結構，用於處理一些不交集（Disjoint sets，一系列沒有重複元素的集合）的合併及查詢問題。併查集支持如下操作：

• 查詢：查詢某個元素屬於哪個集合，通常是返回集合內的一個「代表元素」。這個操作是為了判斷兩個元素是否在同一個集合之中。
• 合併：將兩個集合合併為一個。
• 添加：添加一個新集合，其中有一個新元素。添加操作不如查詢和合併操作重要，常常被忽略。

添加了8個元素，每個元素位於它自己的集合中。

在幾次合併操作後，一些集合合併在一起。

由於支持查詢和合併這兩種操作，併查集在英文中也被稱為聯合-查找數據結構（Union-find data structure）或者合併-查找集合（Merge-find set）。

「併查集」可以用來指代任何支持上述操作的數據結構，但是一般來說，「併查集」特指其中最常見的一種實現：不交集森林（Disjoint-set forest）。經過優化的不交集森林有線性的空間複雜度（$\mathrm {O} \left(n\right)$，$n$為元素數目，下同），以及接近常數的單次操作平均時間複雜度（$\mathrm {O} \left(\alpha \left(n\right)\right)$，$\alpha$為反阿克曼函數），是效率最高的常見數據結構之一。

併查集是用於計算最小生成樹的克魯斯克爾演算法中的關鍵。由於最小生成樹在網絡路由等場景下十分重要，併查集也得到了廣泛的引用。此外，併查集在符號計算，寄存器分配等方面也有應用。

不交集森林

表示

不交集森林把每一個集合以一棵樹表示，每一個節點即是一個元素。節點保存着到它的父節點的引用，樹的根節點則保存一個空引用或者到自身的引用或者其他無效值，以表示自身為根節點。這個數據結構最早由Bernard A. Galler和Michael J. Fischer於1964年提出，但是經過了數年才完成了精確的分析。

添加

添加操作MakeSet(x)添加一個元素x，這個元素單獨屬於一個僅有它自己的集合。在不交集森林中，添加操作僅需將元素標記為根節點。用偽代碼表示如下：

 function MakeSet(x)
     x.parent := x
 end function

在經過優化的不交集森林中，添加操作還會初始化一些有關節點的信息，例如集合的大小或者秩。

查詢

在不交集森林中，每個集合的代表即是集合的根節點。查詢操作Find(x)從x開始，根據節點到父節點的引用向根行進，直到找到根節點。用偽代碼表示如下：

 function Find(x)
     if x.parent = x then
         return x
     else
         return Find(x.parent)
     end if
 end function

路徑壓縮優化

在集合很大或者樹很不平衡時，上述代碼的效率很差，最壞情況下（樹退化成一條鏈時），單次查詢的時間複雜度高達$\mathrm {O} \left(n\right)$。一個常見的優化是路徑壓縮：在查詢時，把被查詢的節點到根節點的路徑上的所有節點的父節點設置為根結點，從而減小樹的高度。也就是說，在向上查詢的同時，把在路徑上的每個節點都直接連接到根上，以後查詢時就能直接查詢到根節點。用偽代碼表示如下：

 function Find(x)
     if x.parent = x then
         return x
     else
         x.parent := Find(x.parent)
         return x.parent
     end if
 end function

合併

合併操作Union(x, y)把元素x所在的集合與元素y所在的集合合併為一個。合併操作首先找出節點x與節點y對應的兩個根節點，如果兩個根節點其實是同一個，則說明元素x與元素y已經位於同一個集合中，否則，則使其中一個根節點成為另一個的父節點。

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     
     if xRoot ≠ yRoot then
         xRoot.parent := yRoot
     end if
 end function

按秩合併優化

上述代碼的問題在於，可能會使得樹不平衡，增大樹的深度，從而增加查詢的耗時。一個控制樹的深度的辦法是，在合併時，比較兩棵樹的大小，較大的一棵樹的根節點成為合併後的樹的根節點，較小的一棵樹的根節點則成為前者的子節點。

判斷樹的大小有兩種常用的方法，一個是以樹中元素的數量作為樹的大小，這被稱為按大小合併。用偽代碼表示如下：

 function MakeSet(x)
     x.parent := x
     x.size := 1
 end function
 
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     
     if xRoot ≠ yRoot then
         if xRoot.size < yRoot.size then
             large := yRoot
             small := xRoot
         else
             large := xRoot
             small := yRoot
         end if
         
         small.parent := large
         large.size := large.size + small.size
     end if
 end function

需要注意的是，上面的代碼中，只有根節點的size有意義，非根節點的size是沒有意義的。

另一種做法則是使用「秩」來比較樹的大小。」秩「的定義如下：

• 只有根節點的樹（即只有一個元素的集合），秩為0；
• 當兩棵秩不同的樹合併後，新的樹的秩為原來兩棵樹的秩的較大者；
• 當兩棵秩相同的樹合併後，新的樹的秩為原來的樹的秩加一。

容易發現，在沒有路徑壓縮優化時，樹的秩等於樹的深度減一。在有路徑壓縮優化時，樹的秩仍然能反映出樹的深度和大小。在合併時根據兩棵樹的秩的大小，決定新的根節點，這被稱作按秩合併。用偽代碼表示如下：

 function MakeSet(x)
     x.parent := x
     x.rank := 0
 end function
 
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     
     if xRoot ≠ yRoot then
         if xRoot.rank < yRoot.rank then
             large := yRoot
             small := xRoot
         else
             large := xRoot
             small := yRoot
         end if
         
         small.parent := large
         if large.rank = small.rank then
             large.rank := large.rank + 1
         end if
     end if
 end function

同樣，上面的代碼中，只有根節點的rank有意義，非根節點的rank是沒有意義的。

時間及空間複雜度

空間複雜度

容易看出，不交集森林的空間複雜度是$\mathrm {O} \left(n\right)$。

時間複雜度

對於同時使用路徑壓縮和按秩合併優化的不交集森林，每個查詢和合併操作的平均時間複雜度僅為$O(\alpha (n))$，$\alpha (n)$是反阿克曼函數。由於阿克曼函數$A$增加極度迅速，所以$\alpha (n)$增長極度緩慢，對於任何在實踐中有意義的元素數目$n$，$\alpha (n)$均小於5，因此，也可以粗略地認為，併查集的操作有常數的時間複雜度。

實際上，這是漸近最優算法：Fredman 和 Saks 在 1989 年證明了任何併查集都需要 $\Omega (\alpha (n))$ 的均攤時間來完成每次操作。