在計算機科學(xué)中，并查集（英文：Disjoint-set data structure，直譯為不交集數(shù)據(jù)結(jié)構(gòu)）是一種數(shù)據(jù)結(jié)構(gòu)，用于處理一些不交集（Disjoint sets，一系列沒有重復(fù)元素的集合）的合并及查詢問題。并查集支持如下操作：
由于支持查詢和合并這兩種操作，并查集在英文中也被稱為聯(lián)合-查找數(shù)據(jù)結(jié)構(gòu)（Union-find data structure）或者合并-查找集合（Merge-find set）。
并查集是用于計算最小生成樹的迪杰斯特拉算法中的關(guān)鍵。由于最小生成樹在網(wǎng)絡(luò)路由等場景下十分重要，并查集也得到了廣泛的引用。此外，并查集在符號計算，寄存器分配等方面也有應(yīng)用。
設(shè)計一個算法大致分為六個步驟：
我們從一個基本問題：網(wǎng)絡(luò)連通性（Network connectivity）出發(fā)，該問題可以抽象為：
并查集的對象可以是下面列出的任何類型：
圖 1 連通圖
在編程的時候，為了方便起見，我們對這些對象從 0 到 n-1 進行編號，從而用一個整形數(shù)字表示對象。隱藏與 Union-find 不相關(guān)的細節(jié)；可以使用整數(shù)快速獲取與對象相關(guān)的信息（數(shù)組的下標(biāo)）；可以使用符號表對對象進行轉(zhuǎn)化。
簡化有助于我們理解連通性的本質(zhì)。
如圖 1 所示，假設(shè)我們有編號為 [0,1,2,3,4,5,6,7,8,9] 的 10 個對象，對象的不相交集合為 : {{0},{1},{2,3,9},{5,6},{7},{4,8}} 。
Find 查詢：2 和 9 是否在一個集合當(dāng)中呢？
答：{{0},{1},{2,3,9},{5,6},{7},{4,8}} 。
Union 命令：合并包含 3 和 8 的集合。
答：{{0},{1},{2,3,4,8,9},{5,6},{7}} 。
連接組件(Connected Component)：一組相互連接的頂點.
每一次 Union 命令會將組（連通分量）的數(shù)量減少 1 個。
如上圖所示，初始時，每一個頂點為一個組，我們執(zhí)行了 7 次 Union 操作后，變成了 3 個組。其中 {2 9} 不算做一次 Union 操作，是因為在 Union 之前，我們使用 Find 查找命令，會發(fā)現(xiàn) {2 9} 此時已經(jīng)位于同一個組 {2 3 4 5 6 9} 當(dāng)中。
以網(wǎng)絡(luò)連通性問題為例，如下圖所示，find(u,v) 可以判斷頂點 u 和 v 是否聯(lián)通？
如下圖所示，圖中共包含 63 個組，其中對象 u 和 對象 v 在同一個集合當(dāng)中，我們可以找到一條從對象 u 到對象 v 的路徑（紅色路線）但是我們并不關(guān)心這條路勁本身，只關(guān)心他們是否聯(lián)通：
上面的問題看似很復(fù)雜，但也很容易抽象為 Union-Find 模型：
現(xiàn)在目標(biāo)就是為 Union-Find 設(shè)計一個高效的數(shù)據(jù)結(jié)構(gòu)：
設(shè)計一個大小為 N 的整型數(shù)組 id[]，如果 p 和 q 有相同的 id ，即 id[p] = id[q]，則認(rèn)為 p 和 q 是聯(lián)通的，位于同一個集合中，如下圖所示，5 和 6 是聯(lián)通的，2、3、4 和 9 是聯(lián)通的。
Find(p,q) 查詢操作只需要判斷 p 和 q 是否具有相同的 id，即 id[p] 是否等于 id[q] ；比如查詢 Find(2,9)，id[2] = id[9] = 9 ，則 2 和 9 是聯(lián)通的。
Union(p,q) 操作：合并包含 p 和 q 的所有組，將輸入中所有 id 為 id[p] 的對象 id 修改為 id[q]。比如 Union(3,6) ，需要將 id 為 id[3] = 9 的所有對象 {2,3,4,9} 的 id 均修改為 id[6] = 6 ，如下圖所示。
Find(u,v) 的時間復(fù)雜度為 ，Union(p,q) 的時間復(fù)雜度為 量級 ，每一次 Union 操作需要更新很多元素 i 的 index id[i] 。
以下圖為例，我們依次執(zhí)行 Union(3,4)， Union(4,9)， Union(8,0)， Union(2,3)，......，Union(6,1) 操作，整形數(shù)組 id[] 中元素的變化過程。
public class QuickFind
{
private int[] id;
public QuickFind(int N)
{
id = new int[N];
for (int i = 0; i < N; i++){
id[i] = i;
}
}
public boolean find(int p, int q)
{
return id[p] == id[q];
}
public void unite(int p, int q)
{
int pid = id[p];
for (int i = 0; i < id.length; i++) {
if (id[i] == pid) {
id[i] = id[q];
}
}
}
}
Quick-find 算法的 find 函數(shù)非常簡單，只是判斷 id[p] == id[q] 并返回，時間復(fù)雜度為 ，而 Union(u,v) 函數(shù)因為無法確定誰的 ID 與 id[q] 相同，所以每次都要把整個數(shù)組遍歷一遍，如果一共有 個對象，則時間復(fù)雜度為 。綜合一下，表示如果 Union 操作執(zhí)行 次，總共 個對象（數(shù)組大小），則時間復(fù)雜度為 量級，。
因為這個算法 Find 操作很快，而 Union 操作卻很慢，所以將其稱為 Quick-Find 算法。
回憶 Quick-Find 中 union 函數(shù)，就像是暴力法，遍歷所有對象的 id[] ，然后把有著相同 id 的數(shù)全部改掉， Quick-Union 算法則是引入 “樹” 的概念來優(yōu)化 union 函數(shù)，我們把每一個數(shù)的 id 看做是它的父結(jié)點。比如說，id[3] = 4，就表示 3 的父結(jié)點為 4。
與 Quick-Find 算法使用一樣的數(shù)據(jù)結(jié)構(gòu)，但是 id[] 數(shù)組具有不同的含義：
id[]id[i] 表示 i 的父結(jié)點i 的根結(jié)點為 id[id[id[...id[i]...]]]如圖所示，id[2] = 9 就表示 2 的父結(jié)點為 9；3 的根節(jié)點為 9 (3 的父結(jié)點為 4，4 的父結(jié)點為 9，9的父結(jié)點還是 9，也就是根結(jié)點了)，5 的根結(jié)點為 6 。
那么 Find(p,q) 操作就變成了判斷 p 和 q 的根結(jié)點是否相同，比如 Find(2,3) ，2 和 3 的根結(jié)點 9 相同，所以 2 和 3 是聯(lián)通的。
Union(p,q) 操作就是將 q 根結(jié)點的 id 設(shè)置為 p 的根結(jié)點的 id。如上圖所示，Union(3,5) 就是將 5 的根結(jié)點的 6 設(shè)置為 3 的根結(jié)點 9 ，即 id[5] = 9 ，僅更新一個元素的 id 。
對于原數(shù)組 i = {0,1,2,3,4,5,6,7,8,9} 及 id 數(shù)組 id[10] = {0,1,2,3,4,5,6,7,8,9} ，依次執(zhí)行 Union(3,4) ，Union(4,9) ，Union(8,0) ，Union(2,3) ，Union(5,6) ，Union(5,9) ，Union(7,3) ，Union(4,8) ，Union(6,2) 的過程中如下：
public class QuickUnion
{
private int[] id;
public QuickUnion(int N) {
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}
private int root(int i) {
while (i != id[i]) i = id[i];
return i;
}
public boolean find(int p, int q) {
return root(p) == root(q);
}
public void unite(int p, int q) {
int i = root(p);
int j = root(q);
id[i] = j;
}
}
對于 Find(p,q) 操作，只需要找到 p 的根結(jié)點和 q 的根結(jié)點，檢查它們是否相等。合并操作就是找到兩個根節(jié)點并將第一個根節(jié)點的 id 記錄值設(shè)為第二個根節(jié)點 。
與 Quick-Find 算法相比， Quick-Union 算法對于問題規(guī)模較大時是更加高效。不幸的是，Quick-Union 算法快了一些但是依然太慢了，相對 Quick-Find 的慢，它是另一種慢。有些情況下它可以很快，而有些情況下它還是太慢了。但 Quick-Union 算法依然是用來求解動態(tài)連通性問題的一個快速而優(yōu)雅的設(shè)計。
Quick-Union 算法的缺點在于樹可能太高了。這意味著查找操作的代價太大了。你可能需要回溯一棵瘦長的樹（斜樹），每個對象只是指向下一個節(jié)點，那么對葉子節(jié)點執(zhí)行一次查找操作，需要回溯整棵樹，只進行查找操作就需要花費 N 次數(shù)組訪問，如果操作次數(shù)很多的話這就太慢了。
Find 操作：最好時間復(fù)雜度為 ，最壞為 ，平均 。
Union 操作：最好時間復(fù)雜度為 ，最壞為 ，平均
當(dāng)進行 次 Union 操作，那么平均時間復(fù)雜度就是 。
好，我們已經(jīng)看了快速合并和快速查找算法，兩種算法都很容易實現(xiàn)，但是不支持巨大的動態(tài)連通性問題。那么，我們該怎么改進呢？
一種非常有效的改進方法，叫做加權(quán)。也許我們在學(xué)習(xí)前面兩個算法的時候你已經(jīng)想到了。這個改進的想法是在實現(xiàn) Quick-Union 算法的時候執(zhí)行一些操作避免得到一顆很高的樹。
如果一棵大樹和一棵小樹合并，避免將大樹放在小樹的下面，就可以一定程度上避免更高的樹，這個加權(quán)操作實現(xiàn)起來也相對容易。我們可以跟蹤每棵樹中對象的個數(shù)，然后我們通過確保將小樹的根節(jié)點作為大樹的根節(jié)點的子節(jié)點以維持平衡，所以，我們避免將大樹放在小樹下面的情況。
如上圖所示，以 Union(5,3) 為例，5 的根結(jié)點為 6，3 的根結(jié)點為 9 ：
我們可以看一下 Weighted Quick-Union 操作的例子：
可以看到 Weighted Quick-Union 所生成的樹很 “胖”，剛好滿足我們的需求。
Weighted Quick-Union 的實現(xiàn)基本和 Quick-Union 一樣，我們只需要維護一個數(shù)組 sz[] ，用來保存以 i 為根的樹中的對象個數(shù)，比如 sz[0] = 1 ，就表示以 0 為根的樹包含 1 個對象。
public class WeightedQuickUnion
{
private int[] id;
private int[] sz;
public WeightedQuickUnion(int N) {
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
sz[i] = 1; // 初始時，每一個結(jié)點為一棵樹，sz[i] = 1
}
}
private int root(int i) {
while (i != id[i]) i = id[i];
return i;
}
public boolean find(int p, int q) {
return root(p) == root(q);
}
public void unite(int p, int q) {
int i = root(p);
int j = root(q);
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
}
}
對于加權(quán) Quick-Union 算法處理 個對象和 條連接時最多訪問 次，其中 為常數(shù)，即時間復(fù)雜度為 量級。與 Quick-Find 算法（以及某些情況下的 Quick-Union 算法）的時間復(fù)雜度 形成鮮明對比。
Find 操作：
Union 操作：
Union-Find 算法是在 Weighted Quick-Union 的基礎(chǔ)之上進一步優(yōu)化，即路徑壓縮的 Weighted Quick-Union 算法。Weighted Quick-Union 算法通過對 Union 操作進行加權(quán)保證 Quick-Union 算法可能出現(xiàn)的 “瘦高” 情況發(fā)生。而 Union-Find 算法是通過路徑壓縮進一步將 Weighted Quick-Union 算法的樹高降低。
所謂 路徑壓縮 ，就是在計算結(jié)點 i 的根之后，將回溯路徑上的每個被檢查結(jié)點的 id 設(shè)置為**root(i)**。
如下圖所示，root(9)=0 ，從結(jié)點 9 到根結(jié)點 0 的路徑為 9→6→3→1→0 ，則將 6,3,1 的根結(jié)點設(shè)置為 0 。這樣一來，樹的高度一下子就變矮了，而且對于 Union 和 Find 操作沒有任何影響。
路徑壓縮：
root() 中添加第二個循環(huán)，將每個被遍歷到的結(jié)點的的 id 設(shè)置為根結(jié)點。private int root(int i) {
int root = i;
// 找到結(jié)點 i 的根結(jié)點 root
while (root != id[root]) root = id[root];
// 每個被遍歷到的結(jié)點的的 id 設(shè)置為根結(jié)點 root
while (i != root) {
int tmp = id[i];
id[i] = root;
i = tmp;
}
return root;
}
id[i] = id[id[i]] 。private int root(int i) {
while (i != id[i]) {
id[i] = id[id[i]]; // 簡化的方法
i = id[i];
}
return i;
}
在實踐中，我們沒有理由不選擇簡化的方式，簡化的方式同樣可以使樹幾乎完全平坦，如下圖所示：
定理：從一個空數(shù)據(jù)結(jié)構(gòu)開始，對 個對象執(zhí)行 次 Union 和 Find 操作的任何序列都需要 時間。時間復(fù)雜度的具體證明非常困難，但這并不妨礙算法的簡單性！
路徑壓縮的加權(quán) Quick-Union （Weigthed Quick-Union with Path Compression）算法雖是最優(yōu)算法，但是并非所有操作都能在常數(shù)時間內(nèi)完成。也就是，WQUPC 算法的每個操作在最壞情況下（即均攤后）都不是常數(shù)級別的，而且不存在其他算法能夠保證 Union-Find 算法的所有操作在均攤后都是常數(shù)級別。
| 算法 | Union | Find | 最壞時間復(fù)雜度 |
|---|---|---|---|
| Quick-Find | N | 1 | MN |
| Quick-Union | tree Height | tree Height | MN |
| Weighted Quick-Union | lg N | lg N | N+MlogN |
| WQUPC | Very near to 1 (amortized) | Very near to 1 (amortized) | (N+M)logN |
對于大規(guī)模的數(shù)據(jù)，比如包含 個頂點， 條邊的圖，WQUPC 可以將時間從 3000 年降低到 1 分鐘之內(nèi)就可以處理完，而這是超級計算機也無法匹敵的。對于同一問題，使用一部手機運行的 WQUPC 輕松擊敗在超級計算機 上運行的Quick-Find 算法，這也許就是算法的魅力。
