abstract

并查集（Union-Find Set）是一種數據結構，主要用于處理動態連通性問題（Dynamic Connectivity Problem），例如在圖論中判斷兩點是否屬于同一個連通分量，以及動態地合并集合。

它廣泛應用于解決最小生成樹（Minimum Spanning Tree）、網絡連接問題等領域。

并查集的概念

并查集是一種簡單的集合表示，它支持以下3種操作：

1. Initial(S)：將集合S中的每個元素都初始化為只有一個單元素的子集合。
2. Union(S, Root1, Root2)：把集合S中的子集合Root2并入子集合Root1。要求Root1和Root2不相交，否則不執行合并。
3. Find(S, x)：找到集合S中單元x所在的子集合，并返回該子集合的根結點。

集合和動態連通性

并查集維護的是一些不相交的集合（Disjoint Sets）

例如，有元素集合 {1, 2, 3, 4, 5}，可以有如下集合劃分：

• 初始狀態：{ {1}, {2}, {3}, {4}, {5} }
• 合并 {1} 和 {2}：{ {1, 2}, {3}, {4}, {5} }
• 再合并 {3} 和 {4}：{ {1, 2}, {3, 4}, {5} }
• 判斷 1 和 2 是否屬于同一集合：否

并查集的存儲結構

通常用樹的雙親表示法作為并查集的存儲結構，每個子集合是一棵樹表示。

所有表示子集合的樹，構成一個森林。存放在雙親表示數組內

通常使用數組元素的下標代表集合中的元素(名字),用根節點的下標代表子集合名字

樹中每個結點的雙親指針指向父節點，根結點的雙親指針為負數（可設置為該集合元素數量的相反數）。

在采用樹的雙親指針數組表示作為并查集的存儲表示時，集合元素的編號從0到SIZE-1。
其中SIZE是最大元素的個數。

---

初始化示例

集合 S = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } S=\set{0,1,2,3,4,5,6,7,8,9} S={0,1,2,3,4,5,6,7,8,9},初始時每個元素自成一個單元素子集合。

數組表示：

下標	0	1	2	3	4	5	6	7	8	9
父節點	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1

---

子集合的合并示例

例如,經過一定計算，子集合并為3個更大的子集合：

• S 1 = { 0 , 6 , 7 , 8 } S_1 = \set{0, 6, 7, 8} S1?={0,6,7,8}
• S 2 = { 1 , 4 , 9 } S_2 = \set{1, 4, 9} S2?={1,4,9}
• S 3 = { 2 , 3 , 5 } S_3 = \set{2, 3, 5} S3?={2,3,5}

樹狀表示：

三個子集的名字分別用根節點$0,1,2$表示

例如,在存儲結構(雙親表示)中,元素(結點)$6,7,8$的雙親結點為結點$0$;于是在雙親表示數組中,下標為$6,7,8$的數組分量中的值都指示$0$,表明結點$6,7,8$處在結點$0$所表示的子集中(子集名為0),而結點0本身對應的數組分量存放的是子集0中包含的元素數量的相反數(是個負數)

其余兩個子集類似

數組表示：

下標	0	1	2	3	4	5	6	7	8	9
父節點	-4	-3	-3	2	1	2	0	0	0	1

說明：

• 負數表示根結點，數值是集合中元素的數量（取反）。
• 例如下標 0 的值 -4 表示集合 $S_1$ 包含4個元素。

---

集合的合并操作

為將兩個子集合合并，需將其中一個集合的根結點的雙親指針指向另一個集合的根結點。

例如合并 $S_{12}=S_1\cup S_2$ ，結果如下：

樹狀表示：

下標	0	1	2	3	4	5	6	7	8	9
父節點	-7	0	-3	2	1	2	0	0	0	1

說明：

可以看到,在這類合并操作執行后,雙親表示數組中,如果要找到元素4所在集合$S_{12}$的根節點,就不能保證S[4]是所需要的答案(本例中S[4]=1不是$S_{12}$的根節點;需要繼續向上跟蹤,再次訪問S[S[4]]=S[1]=0,0還不是負數,所以要再次跟蹤,S[0],發現S[0]=-7,由此可知0就是最初元素4所在子集合的根節點

這種改變讓查詢變得不夠直接,可以通過路徑壓縮操作來改進

并查集的基本實現

并查集的結構定義如下：

#define SIZE 100
int UFSets[SIZE]; //集合元素數組 (雙親指針數組)

下面是并查集主要運算的實現。
（1）并查集的初始化操作(雙親表示數組中對應分量設置為-1,表示初始每個子集僅有一個元素)

void Initial(int S[]) {for(int i=0; i<SIZE; i++)//每個元素自成單元素集合S[i] = -1;
}

（2）并查集的Find操作
在并查集S中查找并返回包含元素x的樹的根。

int Find(int S[], int x) {while(S[x] >= 0)//循環尋找x,直到S[x]是負數為止(離開循環時,x是非負的,S[x]是負數)x = S[x];//更新x(這里保證x是非負的)return x;//返回非負的值,表示元素x所在子集的根節點
}

判斷兩個元素是否屬于同一集合，只需分別找到它們的根，再比較根是否相同即可。
（3）并查集的Union操作
求兩個不相交子集合的并集。

若將兩個元素所在的集合合并為一個集合，則需要先找到兩個元素的根，再令一棵子集樹的根指向另一棵子集樹的根。

void Union(int S[], int Root1, int Root2) {if(Root1 == Root2) return;//兩個根相同不合并S[Root2] = Root1;//根不同,將用其中一個根Root2的雙親結點指向另一個根Root1
}

小結

Find操作和Union操作的時間復雜度分別為O(d)和O(1)，其中d為樹的深度。

并查集實現的優化

在極端情況下，$n$個元素構成的集合樹的深度為n，則Find操作的最壞時間復雜度為O(n)。

改進的辦法是：在做Union操作之前，首先判別子集中的成員數量，然后令成員少的根指向成員多的根，即把小樹合并到大樹，為此可令根結點的絕對值保存集合樹中的成員數量。
（1）改進的Union操作

void Union(int S[], int Root1, int Root2) {if(Root1 == Root2) return;//(負數的絕對值越小,值越大abs(S[Root2])<abs(S[Root1],則S[Root2] > S[Root1])if(S[Root2] > S[Root1]) { // Root2 結點數更少)S[Root1] += S[Root2]; // 累加集合樹的結點總數S[Root2] = Root1;      // 小樹合并到大樹} else {S[Root2] += S[Root1]; // 累加結點總數S[Root1] = Root2;     // 小樹合并到大樹}
}

采用這種方法構造得到的集合樹，其深度不超過${\log }_{2}n+1$(這里$n$為元素數量)

隨著子集逐對合并，集合樹的深度越來越大，為了進一步減少確定元素所在集合的時間，還可進一步對上述Find操作進行優化，當所查元素$x$不在樹的第二層時，在算法中增加一個“壓縮路徑”的功能，即將從根到元素x路徑上的所有元素都變成根的孩子。

例如$root,p_1,p_2,...,p_m,x,...$,通過壓縮操作,比如依次將$x,p_m,?,p_2,p_1$掛到$root$結點下;

而掛到root結點下這個操作對于雙親表示法,就是將對應的結點的數組分量(父節點)設置為root;

(2)改進find操作

int Find(int S[], int x) {int root=x;//根節點編號初始化為x//找到x所在子集根節點while(s[root]>=0)root=s[root];//這時候已經找到root了,但是為了之后的新查找更快,做路徑壓縮while(x!=root){//壓縮路徑(將樹的高于第2層的結點進行壓縮)int t=S[x];//t指向x的父節點(以便于處理完x沿著路徑往祖先結點繼續處理)S[x]=root;//x直接掛到根節點下面x=t;//更新下一個需要處理的目標}return root;//返回根節點編號
}

通過 Find 操作的“壓縮路徑”優化后，可使集合樹的深度不超過 $O(\alpha (n))$，其中 $\alpha (n)$ 是一個增長極其緩慢的函數，對于常見的正整數 $n$，通常 $\alpha (n)\le 4$。