併查集

<image>

<image>

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

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

由於支持查詢和合併這兩種操作，併查集在英文中也被稱為聯合-查找數據結構（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))$ 的均攤時間來完成每次操作。