假設八部電腦之間的連線逐一加入。連接 0 與 1,再連接 1 與 2 後,即使 0 與 2 之間沒有直接連線,我們也應知道它們屬於同一個連通群組。每次新增連線後都重新列出各組全部成員,所做的工作比這個問題真正需要的多。不相交集合結構只記錄足以辨認及合併群組的數據。
關鍵是分清哪些元素屬於同一組,以及用甚麼指標表示這件事。查詢可以重新整理指標,而不改變任何群組。反過來,一次成功合併可能只改一個父指標,卻已改變了群組。始終同時看清這兩個層次,算法便較容易證明及除錯。
先定義劃分與操作
定義 1.1.1
(劃分與不相交集合操作)
全集 的一個劃分,是一族非空、兩兩不相交的子集,而它們的聯集是 。每個元素因此恰好屬於一個子集,稱為其集合或分量。
對 ,初始化時每個元素各自成為單元素集合。find(x) 傳回包含 的集合的代表元。若 x、y 所屬集合不同,unite(x,y) 便合併兩者。在這個抽象意義下,兩個元素連通,恰好等價於目前代表元相等。
例如, 是 的一個劃分。它不是圖的邊清單,而是考慮連通性後所得的群組。關係「屬於同一集合」具有自反性、對稱性及遞移性。
| 操作 | 抽象結果 | 會否改變劃分? |
|---|---|---|
find(x) | 所屬集合的目前代表元 | 不會 |
connected(x,y) | 代表元是否相等 | 不會 |
unite(x,y) | 是否合併了兩個不同集合 | 會,而且恰好在傳回真時改變 |
sizeOf(x) | 所屬集合的元素數目 | 不會 |
代表元是實作的選擇,並非應用程式物件的永久名稱。後來的合併可以改變它;尤其不必是集合內最小的元素。
概念視角結構
把合併看成劃分的上確界
按細分關係為 的劃分排序:若 的每個塊都含於 的某個塊內,則 。於是 unite(x,y) 把 換成 之上、使 與 同屬一塊的最小劃分。因此,一連串合併之後的劃分只取決於合併了哪些配對,與次序及重複無關,雖然父森林確實取決於它們。例如,合併 無論先後都得到 ,但按下文的按大小合併規則(平手時保留標號較小的根),父陣列分別是 [0,0,0] 與 [1,1,1]。
用父指標森林表示劃分
以陣列 parent 儲存父指標。根滿足 parent[r] == r;其他元素的指標則通向分量的根。除了根指向自己的指標,父邊形成沒有環的樹。由任何元素沿父指標前進,都必須到達唯一的根。兩個元素屬於同一分量,當且僅當路徑到達同一根。
在根上,size[r] 記錄整個分量的大小,而不是直接子節點數目,也不是某條可見分支的大小。非根的大小項目不會被當作分量大小使用。起初 parent[x] = x、size[x] = 1,分量數目為 。
例題 1.1.2
(建立森林,不必每次把所有分支展平)
使用八個元素。每次把較小分量接到較大分量之下;大小相等時,保留標號較小的根。由單元素集合開始,依次執行:
| 合併 | 保留的根 | 合併後分量大小 | 餘下分量數目 |
|---|---|---|---|
unite(0,1) | |||
unite(2,3) | |||
unite(0,2) | |||
unite(4,5) | |||
unite(6,7) | |||
unite(4,6) | |||
unite(0,4) |
每次調用連接的是根,並不自動把其他每個節點都改為直接指向保留的根。最後的父指標如下:
| 元素 | ||||||||
|---|---|---|---|---|---|---|---|---|
| 父節點 |
7 的路徑是 ,3 的路徑則是 。路徑長度不同,不表示分量不同:兩者都到達 0。目前只有根 0 記錄分量大小 8。
路徑壓縮改變表示,不改變成員歸屬
find(7) 的第一趟遍歷沿三條父邊找到根 0。完整路徑壓縮再把已遍歷元素改為直接指向該根。7 與 6 的父指標改為 0;4 的項目本來就是 0,數值不變。其他項目維持原狀。第二次 find(7) 只需沿 這一條邊前進。
以下的尋根步數,只計第一趟沿父邊前往根的遍歷。不計根指向自己的指標,也不計第二趟壓縮;下方實作的壓縮階段還會沿舊路徑走一遍。只有前後數值不同,才計作一個已改變的父指標項目。按這些約定,第一次查詢尋根走三步、改兩項;第二次尋根走一步、不改任何項目。這些計數描述的是此預先建立的例子,並非每次查詢都有常數最壞時間的證明。
命題 1.1.3
(路徑壓縮保留劃分)
設 find(x) 把所有經過的元素的父指標改為它找到的根 。改動之後,每個元素的根都與之前相同,所以父森林所表示的劃分以及各根上的計數器都沒有改變。
證明
(為何壓縮保留每個所表示的集合)
假設已遍歷元素 原本就到達根 。把其父節點改為 ,不會改變目的地,也不會產生非平凡環: 是根,其路徑不會經過某個不同的後代再返回。
其他元素若原本沿路徑到達 ,現在只是以較短的後續路徑到達同一根 。完全不經過改寫元素的路徑則不變。因此,每個元素在壓縮前後的根都相同,以根相等所表示的劃分完全一致。沒有分量增加或失去成員,所以根的大小計數仍正確。
這就解釋了為何 find 可以修改父指標陣列,卻在抽象層次仍是查詢。它改善的是表示方式,沒有合併或拆開集合。
一起實作連接根與路徑壓縮
以下完整 C++ 例子假設 ,每次操作都接收 內的既有標號。類別只在建立時產生單元素集合;之後支援合併,不支援刪除元素或分開分量。
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
class DisjointSet {
std::vector<int> parent, size;
int components;
public:
explicit DisjointSet(int n) : parent(n), size(n, 1), components(n) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (parent[x] != x) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
bool unite(int x, int y) {
int a = find(x), b = find(y);
if (a == b) return false;
if (size[a] < size[b] || (size[a] == size[b] && a > b)) {
std::swap(a, b);
}
parent[b] = a;
size[a] += size[b];
size[b] = 0;
--components;
return true;
}
bool connected(int x, int y) { return find(x) == find(y); }
int sizeOf(int x) { return size[find(x)]; }
int count() const { return components; }
};
int main() {
DisjointSet sets(8);
for (auto edge : std::vector<std::pair<int, int>>{
{0, 1}, {2, 3}, {0, 2}, {4, 5}, {6, 7}, {4, 6}, {0, 4}}) {
sets.unite(edge.first, edge.second);
}
std::cout << sets.find(7) << ' ' << sets.count() << ' '
<< sets.sizeOf(7) << '\n';
}
輸出是 0 1 8:代表元為 0,只有一個分量,內有八個成員。在 find 中,先用 next 保存舊父節點,再覆寫指標;否則第二趟遍歷會失去原路徑。把原本已等於 root 的父指標再次賦值並無問題,但不屬於前述數值有改變的事件。
在 unite 中,比較大小前,a 與 b 都是根。連接兩個不同的根,恰好合併兩棵樹,也不會產生環,因為兩根原本屬於不同樹。合計大小並把分量數減一,便記錄了這次成功合併。清空 size[b] 是標示該計數已過時;sizeOf 只讀取根上的項目。
若兩次查找傳回同一根,方法回傳假,劃分與分量數目不變。不過,在作出決定前,兩次查找仍可能已壓縮路徑。「沒有新的合併」不等於「沒有寫入任何父指標」。
例題 1.1.4
(多餘的合併仍會寫入父指標)
由上面的父陣列 [0,0,0,2,0,4,4,6] 出發,調用 unite(7,4)。find(7) 走過 ,共三步,並把 parent[7] 與 parent[6] 改為 0;parent[4] 本來就是 0。find(4) 走一步。兩個根都是 0,所以 unite 返回 false,分量數仍是 1,size[0] 仍是 8。陣列卻已變成 [0,0,0,2,0,4,0,0]。沒有發生合併,但父指標被寫入了。
常見錯誤
(比較父指標而不是比較根)
在 [0,0,0,2,0,4,4,6] 中,parent[3]=2、parent[1]=0,兩者不相等,但 1 與 3 屬於同一分量。連通測試必須比較 find(1) 與 find(3),兩者都等於 0。
常見錯誤
(在非根元素上讀取大小計數器)
實作在連接時會清除被連接的根的計數器:unite(2,3) 之後,size[3] 為 0,然而 3 所在的分量有 8 個元素。分量大小必須用 sizeOf(3) 讀取,即 size[find(3)]。
反例模式
隨意改一個父指標,可以拆散舊集合
假設 parent = [0, 0, 1, 3],它表示 及 。錯誤的 unite(2,3) 實作若直接指定 parent[2] = 3,新的根便表示 及 。2 被從舊夥伴中拆走,並沒有把兩個完整集合合併。
應先找到根 0 與 3,再把一個根連到另一個之下。按所示實作,查找 2 先把其父指標壓縮為 0;大小規則再把 3 接到 0,得到 [0, 0, 0, 0] 及一個集合 。舊成員仍到達相同根,關係沒有失去。不相交集合合併的是整個等價類;不能只因引數給了非根元素,就拆散原有類別。
用倍增證明深度上界
定理 1.1.5
(按大小合併限制深度)
設每次合併都把較小分量的根連到另一個分量的根之下,大小相等時任選其一。則在含 個元素的全集中,每個元素的深度至多為 ,所以每次 find 需時 。
證明
(按大小合併限制深度增加的次數)
先考慮沒有路徑壓縮的合併。只有當某元素所屬分量的根被接到另一個根之下,該元素深度才增加一。若原分量大小為 ,大小規則保證它接到大小至少為 的分量。因此,新分量大小至少是 。
由單元素集合開始,經過 次這種深度增加,所屬分量至少有 個元素。全集只有 個元素,所以對 有
因此,沿路徑找到根需要 時間。壓縮只會縮短路徑,故不會令這個上界失效。兩趟 find 的時間,至多是所走路徑長度的常數倍;一次合併則作兩次這樣的查找,再作固定數量的額外工作。
八元素例子在壓縮前,元素 7 的深度達到三,恰好是 。重複查詢已壓縮的路徑可以便宜得多。要分析多次操作更精細的攤銷成本,仍需要另一個論證,不能只看見第二條路徑較短便下結論。
證明透視
為甚麼按大小合併能使分量大小翻倍
整個證明只靠一個不等式:被連接的那棵樹不比接收它的樹大,所以被連接的元素落入的分量,大小至少是原來的兩倍。它只作用於被連接那棵樹的元素;接收的樹中元素的深度不變。路徑壓縮只用一句話處理:它只會降低深度,因此即使部分路徑已被縮短,深度也不會超過深度增加的次數。
這條規則不能去掉。若 unite(x,y) 總是把 所在集合的根連到 所在集合的根之下,則依次調用 unite(0,1)、unite(1,2)、、unite(n-2,n-1) 會建成鏈 ,而 find(0) 需走過 條邊。
初始化需要 時間,兩個陣列佔用 空間。要說明完整操作的成本:已知根之後,連接根只需常數工作;unite(x,y) 卻必須先把根找出來。
應用到逐步加入邊的連通性
固定頂點集合,由沒有邊及各自獨立的單元素集合開始。每當無向邊 加入,調用 unite(u,v)。
定理 1.1.6
(並查集追蹤逐步加入邊後的連通性)
依此程序,每處理完一條邊之後,兩個頂點的代表元相等,當且僅當已處理的邊能以路徑連接它們。
證明
(每條邊不是連接兩個分量,就是留在同一分量內)
起初,不同頂點之間沒有這種路徑。加入一條邊,可能連接兩個原有連通分量,也可能留在同一分量內。合併操作恰好作出相同區分,因此每次加入邊後都保留不變量。
這證明 connected(u,v) 能回答目前是否連通,卻不會找出圖內的實際路徑。父邊是實作指標,不一定是輸入圖的邊。
在簡單無向圖中,若一條邊的端點本來已連通,它會與原有路徑形成環。因此,不相交集合可用於 Kruskal 的環檢查:按權重非遞減次序處理邊,端點屬於不同集合時才接納。數據結構實作的是這項檢查;要證明所得為最小生成樹,還需要貪婪法的割性質論證,與並查集不變量是不同部分。
例題 1.1.7
(逐條邊判斷接受還是拒絕)
取頂點 ,各自為單元素集合,按次序處理邊 ,使用上面的實作,大小相等時保留標號較小的根。
| 邊 | 兩個根 | 結果 | 之後的分量數 |
|---|---|---|---|
| 接受:1 連到 0 之下 | |||
| 接受:2 連到 0 之下 | |||
| 拒絕:已在同一集合 | |||
| 接受:4 連到 3 之下 | |||
| 接受:3(大小 2)連到 0(大小 3)之下 | |||
拒絕:find(4) 沿 走,並把 parent[4] 設為 0 |
接受了 4 條邊,恰為 ,被拒絕的兩條邊就是會形成環的邊。被拒絕的邊 的兩端在父森林中並不相鄰,卻已被先前接受的邊連通。最後的父陣列是 [0,0,0,0,0]。
反例模式
只靠劃分,不能處理任意刪邊
路徑圖的邊為 ;三角形的邊為 。兩者都得到劃分 。現在各自刪除 :路徑圖分成 與 ,三角形卻仍可經 0 連通。
同一個已儲存劃分及同一項刪除,竟需要不同答案,因為劃分已丟失哪些替代路徑存在的數據。普通並查集不能只把某個父指標賦值反轉,便解決任意刪邊。含刪除的問題需要額外數據或另一個算法,不能無依據地在這個介面加上拆分操作。
練習
快速檢查
(1. 分清查詢的指標改變與答案)
從上面的八元素父指標表開始,尚未作任何壓縮。連續執行兩次 find(3)。寫出每次尋根步數、數值有改變的父指標項目、傳回代表元,以及最後的分量數目。
解答 · 解答 1
第一次路徑是 ,共兩步,只把 parent[3] 由 2 改為 0。第二次路徑是 ,一步,不改任何項目。兩次都傳回 0,仍只有一個分量。其他分支,包括由 7 出發的路徑,都沒有被這兩次調用壓縮。
快速檢查
(2. 成功合併不一定展平新分量)
改由 parent = [0,0,0,2,4,4,4,6] 開始,其中有兩個大小為四的分量,根為 0 及 4。啟用壓縮,執行所實作的 unite(3,7)。最後父指標陣列是甚麼?下一次 find(7) 在壓縮前會走甚麼路徑?
解答 · 解答 2
查找 3 把其父指標改為 0。查找 7 沿 前進,把其父指標改為 4。大小相等,故把根 4 接到根 0 之下。最後陣列是 [0,0,0,0,0,4,4,4],下一次由 7 出發的路徑是 ,共兩步。連接根 4,並沒有自動把它的所有子節點都改為直接指向 0。
快速檢查
(3. 判斷代表元是否必須為最小標號)
一個分量的成員是 ,根為 0;另一分量的成員是 ,根為 4。按大小合併時,哪個根保留?標號較小者優先的平手規則會改變決定嗎?
解答 · 解答 3
保留根 4,因為其分量大小為六,大於二。大小不同,平手規則不適用。所得集合包含 0,代表元卻是 4。比較代表元仍可正確認出分量;選最小標號並非這個結構的抽象契約。
快速檢查
(4. 分清連接根與完整合併的成本)
全集有九個元素並採用按大小合併。按倍增證明,父指標路徑可以有深度四嗎?為甚麼只因操作改一個根指標,就把整個 unite(x,y) 稱為常數時間,並不完整?
解答 · 解答 4
深度四至少需要 個元素,所以按這些規則, 時不可能;上界是 。兩根已知時,連接它們只需常數工作,但發現兩根需要兩次查找。對數上界同時考慮了這些遍歷、壓縮階段及最後的連接。