會改變的劃分
向無向圖逐條加入邊時,分量測試會問兩個端點是否已連通。前面的 Kruskal 單元使用簡單標籤掃描;不相交集合森林則用父指標表示相同劃分,合併時無須重新標記每個頂點。
定義 4.4.1
(不相交集合、find 與 union)
固定 個元素,起初每個元素各自成集合。操作 回傳 所在集合的代表; 合併兩者所在集合。代表不必是最小元素,合併後也可能改變。兩元素在同一集合,當且僅當它們當前的代表相同。
父指標森林與規則
定義 4.4.2
(帶大小標記的父指標森林)
每個元素儲存一個父指標。根指向自身;沿父指標最終到達根。每個根另存其樹的元素數目。起初每個元素都是大小為一的根。查找代表時沿父指標到根;合併時先找兩個根,若相同則不作改變。否則把較小樹的根接到較大樹的根之下,並把兩個大小相加存到保留的根;相等時任意決定。非根所存的大小不需查用。
命題 4.4.3
(森林表示劃分)
經過任何一連串合併之後,森林中的樹恰好是當前的各個集合,而每個根所存的數目就是它的樹的元素個數。
證明
(對操作作歸納的不變量)
起初每棵樹是一個集合,每個根的大小為一。把一個根接到另一個根之下,恰好合併含有這兩個根的兩棵樹;由於兩個根不同,不會形成環。其他樹都不變。這與兩個集合的合併相符。若兩次查找的結果相同,合併不作任何改變,而這兩個元素本來就在同一集合。因此對操作的次數作歸納,可知森林中的樹恰好是當前集合。保留根的大小以加法更新,等於合併後樹的元素個數,所以大小不變量也得以保持。
定理 4.4.4
(不壓縮路徑時的對數深度)
若按大小合併且不使用路徑壓縮,每條父指標路徑最多有 條邊。因此在陣列存取為常數時間的模型下,每次查找以及包含兩次查找的合併均需 時間。
證明
(元素的深度每增加一次,其所在的樹至少倍增)
固定元素 。只有當其當前樹的根接到另一個不同的根之下時, 的深度才增加,而且恰好增加一。接上之前,其樹不大於另一棵樹;接上之後,合併樹至少有先前兩倍元素。在兩次深度增加之間,樹只會變大。從大小一開始且永不超過 ,深度最多增加 次。相同大小時不論選哪個根,證明都成立。一次查找沿一條父指標路徑走,其長度至多是這個深度界,加上讀取根的常數工作;一次合併則作兩次查找和常數量的其他工作。
證明透視
倍增論證用到甚麼
真正起作用的量,是含 的那棵樹的大小。它從一開始,從不超過 ,並在每次使 下降一層的連接時倍增;具備這三個性質的量,只能倍增 次。倍增完全來自連接時的大小規則:由於被移到下面的是較小的樹,含 的樹至多是合併後樹的一半。容許相等,所以平手時怎麼選都無所謂。
若把規則反過來,讓較大的樹接到較小的樹之下, 所在的樹可以很大,而合併後的樹卻只多了一個元素,倍增便失效。這裏的查找從不改變指標,所以除了連接之外,沒有任何步驟會改變深度。一次連接把整棵樹恰好下移一層,因此 的深度就是把它所在的樹下移的連接次數,而從 出發的查找,路徑長度等於這個深度。
操作例子
例題 4.4.5
(追蹤非根父節點)
從單元素集合 開始;相同大小時把第二個所列根接到第一個之下。執行 和 後,根 的大小均為二。執行 後,根 大小為四,而 沿 到根。再合併 ,接著將其大小為二的樹與 的大小四之樹合併:無論參數次序,根 都接到 之下。最後大小為六; 的深度均為二。
例題 4.4.6
(倍增界可以達到)
取八個元素 ,相同大小時把第二個所列根接到第一個之下。依次執行 、、、,得到四個大小為二的根 。再執行 與 ,得到兩個大小為四的根 ,最後 得到大小為八的唯一根 。從 出發的路徑是 ,共三條邊,等於 。這裏每次合併的兩棵樹大小相同,所以每次都把最深的元素再推下一層。
例題 4.4.7
(形成環的邊不改變任何東西)
在六元素的例子中依次插入無向邊 –、–、–,然後是 –。前三次 建成以 為根、大小為四的樹。對 –, 沿 , 沿 ,兩者都回傳 ,所以該次調用不作任何事,大小也不變。這條邊在圖中形成一個環,而分量結構與之前相同:集合 加上 與 。
界的適用範圍
命題 4.4.8
(一連串操作的成本)
初始化陣列需 。之後 次操作的總最壞成本為 ,陣列使用 空間。
證明
(只初始化一次,再逐個操作估算)
把每個元素的父指標設為自身、大小設為一,需要 時間,並使用兩個長度為 的陣列。 次操作中每一次都是一次查找,或是帶兩次查找的一次合併,而按深度定理,每次成本為 。把成本相加即得上界。
對數界來自明確的按大小規則。路徑壓縮會在查找時改變指標,需要另行分析,因此這裏不聲稱反 Ackermann 界。
反例模式
不用大小規則的連接可以造成長鏈
假設每次 都不看大小,直接把 的根接到 的根之下。取 ,依次調用 、,直至 。第一次令 的父節點為 ,第二次令 的父節點為 ,如此類推,所以從 出發的路徑是 ,共七條邊,大於 。在大小規則下,同一串操作仍然很淺:每次調用都把大小為一的樹接到大的根之下,沒有任何路徑多於一條邊。深度定理依賴這條規則;任意接根可產生長鏈,對元素 作一次查找便需七步指標。
常見錯誤
(比較直接父節點而不是根)
在第一個例子中, 的直接父節點是 ,代表卻是 。即使兩個元素的父路徑到達同一個根,只比較直接父節點也可能誤判為不同集合。分量測試必須使用根,而不是只走一步指標。
常見錯誤
(讀取非根的大小)
只有根所存的大小才有意義。在第一個例子中,執行 之後, 仍存著數字二,但它的樹已經屬於一個大小為四、根為 的集合。若之後的合併拿 所存的數字與另一個根的大小比較,可能接錯方向,並破壞倍增論證。必須比較兩個根所存的大小。
若要在插入邊的過程中維護無向連通性,對每條新邊的端點執行合併,查詢時比較兩次查找。
命題 4.4.9
(插入邊時的連通性)
若逐條插入無向圖的邊,且每次插入 時都調用 ,則每次插入之後,所維護的劃分都等於圖的連通分量劃分。
證明
(一次插入要麼合併兩個分量,要麼不改變任何東西)
起初沒有邊,每個頂點各自是一個分量,與單元素集合相符。插入邊 不會在 、 所在分量以外的頂點之間添加任何連通關係。若 與 本來就在同一分量,各分量不變,合併也不作改變。否則兩個分量變成一個,而合併恰好合併對應的兩個集合。對插入次數歸納即得結論。
此結構本身不支援刪邊:刪去橋邊可能把一個已維護集合分成兩個;它也不回答有向可達性,因後者一般不是等價關係。
練習
快速檢查
(大小三的樹與大小七的樹合併,哪個根成為父節點?新大小是多少?)
較小的根接到較大的根之下。
解答 · 答案
把大小三的根接到大小七的根之下;保留根的大小為十。
快速檢查
(當 ,倍增界給出甚麼最大深度?)
套用 。
解答 · 答案
最多 條父邊。
快速檢查
(在例子中,為何 回傳 ,儘管 的直接父節點是 ?)
沿著指標一直往上走。
解答 · 答案
查找沿 到達根 ;中間父指標本身不是代表。
快速檢查
(加入唯一的無向邊 – 後,為何刪除它不能只保持不相交集合結構不變?)
比較刪除前後的連通情況。
解答 · 答案
有該邊時 連通,刪掉後不連通;不變的結構仍把它們放在同一集合,因此需要其他方法或重建。