動機
許多圖算法需要反覆詢問:兩個頂點是否已經被目前選出的邊連通。每加入一條邊就重新計算連通分量,會浪費已有的資訊。不相交集合結構維護頂點集合的一個劃分,並支援兩種操作:查找某個集合的代表元,以及合併兩個集合。
其實作是一片由父指標構成的森林。效率取決於如何連結各棵樹:若總是把一個根接到另一個根之下,可能形成一條很長的鏈;而若把較小的樹接到較大的樹之下,則任何頂點的深度能夠增加的次數都受到限制。倍增論證給出一個具體的對數界,而無需假定更強的反阿克曼函數(inverse-Ackermann)定理。
定義
定義 3.8.1
(不相交集合森林、查找與合併)
開始時有 個單元素集合,每個元素一個。每棵樹的根以自身為父節點;其餘每個節點指向它的父節點。同一棵樹中的元素構成一個集合,根是該集合的代表元。操作 find(x) 從 出發沿父指標走到其根。操作 union(x,y) 先找出兩個根。若兩根不同,則把較小的樹的根連結到較大的樹的根之下,並更新較大根所儲存的大小。大小相等時可任意決定。對已在同一棵樹中的元素做合併,不產生任何改變。
定義 3.8.2
(深度與所儲存的大小)
節點的深度是它到根的路徑上的父邊數目。根所儲存的大小是其所在樹中的元素個數。我們先分析不帶路徑壓縮的按大小合併;之後再把壓縮作為可選的修改來討論。
定理
定理 3.8.3
(按大小合併的高度界)
從 棵單元素樹出發並使用按大小合併,則每個節點的深度至多為 。在父指標模型中,每次查找耗時 ,每次合併(包括其中的兩次查找)耗時 。
定理 3.8.4
(Kruskal 算法的分量測試)
在無向圖中,按邊權非遞減的順序處理各邊,並且當且僅當某條邊的兩個端點具有不同的不相交集合代表元時才接受該邊,則所得結果是一個最小生成森林。對於連通圖,所得結果是一棵最小生成樹。
證明:深度增加迫使集合倍增
證明
(按大小合併使集合在每次深度增加時倍增)
固定一個元素 。只有當 當前所在樹的根被接到另一個根之下時,它的深度才會增加。在這樣的合併中,另一棵樹的節點數至少與 所在的樹一樣多。因此,包含 的新樹的節點數至少是原來的兩倍。此後的合併永遠不會令集合變小。
起初 位於大小為一的樹中,深度為零。經過 次深度增加之後,它所在的樹的大小至少為 。任何樹所含元素都不超過 個,故 ,從而 。這一推理適用於每個元素,儘管不同元素可能在不同的合併中經歷深度增加。
一次查找至多沿著上述數目的父邊前進,再加上最後對根的檢查。一次合併執行兩次查找,以及常數量的大小比較、指標更改和大小更新。由此得到所述的時間界。當 時,沒有可供查找或合併的有效元素;深度的結論針對非空結構。
證明透視
為甚麼較小的樹很重要
這個證明追蹤單一節點,計算它的深度最多能增長多少次。關鍵一步是把每一次增加都歸因於該節點所在集合的一次倍增。只有當節點所在樹的根被連到另一個根之下時,深度才加一;大小規則使接收的樹至少一樣大,所以合併後的集合至少是原來的兩倍。證明用到三件事:大小規則、集合只會合併而不會縮小,以及從單元素開始(大小為一、深度為零)。界 使論證收尾,因為沒有集合可以超過 個元素。若去掉大小規則,大樹就可能被連到單元素之下,使大樹中每個節點的深度加一,而集合只多了一個元素。下面反例中的鏈就是這樣產生的。
證明:不相交集合的不變量
證明
(森林追蹤被接受的邊的連通分量)
在處理任何邊之前,已選的邊構成的圖沒有邊,其連通分量就是單個頂點。不相交集合森林恰好表示這些分量。假設在處理邊 之前這一點成立。
若 與 具有相同的代表元,則已選的邊之中已含有連接它們的一條路徑。加入 會產生圈,所以算法拒絕該邊,分量劃分保持不變。若代表元不同,則加入 會連接兩個分量,且不會形成圈。合併操作恰好合併這兩個被表示的集合,因此不變量依然成立。
證明
(割交換給出最小生成森林)
於是,被接受的邊恰好是 Kruskal 算法所作的無圈選擇。其最優性由標準的割交換論證證明:被接受的邊是穿過當前某個分量所對應的割的最小權邊。任何先前掃描且跨越當前分量的邊,在掃描時兩端也處於不同分量,因為分量只會合併;它因而會被接受。由排序次序,其餘跨割邊的權都不小於當前邊。若包含先前已接受各邊的某個最優生成森林不含該邊,則把它加入後會與另一條權不更小的穿過割的邊形成圈;交換這兩條邊後仍得到生成森林,且其權不增加。通過歸納,可始終保留一個包含所有已接受邊的最優森林。
所有邊都考察完畢後,原圖的每個連通分量都由被接受的邊連通:否則,位於剩餘兩個分量之間某條路徑上的某條原圖的邊,在被掃描時就應當已被接受。因此,被接受的森林在原圖的每個分量中都是生成的,而交換不變量保證其權最小。權相等以及負權都不會令割論證失效。
例題詳解
例題 3.8.5
(一次大小倍增的追蹤)
從單元素集合 開始。合併 ,並另外合併 ;所得的兩棵樹大小均為二。再合併它們的根,平局時把第二個根放在第一個根之下。第二棵樹中的葉子現在深度為二,其所在集合的大小為四。深度界為 。
例題 3.8.6
(一次多餘的合併)
當 和 已在同一棵樹中後,union(a,b) 兩次找到同一個根,不做任何連結。若再次更新大小就是錯誤的:所表示的集合並沒有增加任何元素。所儲存的大小必須始終等於該樹中不同節點的個數。
例題 3.8.7
(Kruskal 算法中的三角形)
對於三角形的邊 ,權分別為 ,接受 並合併 ,然後接受 並合併其所在分量。掃描到 時,其端點具有相同的代表元,因此拒絕該邊。所得生成樹的總權為三。
例題 3.8.8
(一個不連通的圖)
設圖中有一條連接 的權為 的邊,以及一個孤立頂點 。Kruskal 算法接受該邊,並讓 保持為單點樹。答案是一個有兩個分量的最小生成森林,而不是整個圖的生成樹。
路徑壓縮
路徑壓縮修改 find(x):在找到根之後,把途經的節點都重新指向根。它保持所表示的劃分不變:每個被重新導向的指標仍在同一棵樹之內,並且通向同一個根。所儲存的根的大小仍然有效,因為沒有元素改變所屬集合。壓縮在施行的那一刻只會縮短節點的路徑。
按大小合併再加上路徑壓縮可以得到更強的攤還界,但該定理需要另行分析,並需要精確的操作序列模型。上述初等的倍增論證已經給出對數界:在按大小合併引起深度增加之後,包含該節點的集合已經翻倍;壓縮可以去掉一些父邊,但不會產生使深度增加的新父邊。我們在此不推導也不聲稱更強的界。
代表元是實作上的選擇。兩次都正確的運行如果平局處理方式不同,可能為同一個集合給出不同的根。程式應當比較同一結構內返回的代表元,而不應依賴某個特定頂點永遠是某個連通分量的名稱。
常見錯誤
反例模式
任意連結可能產生一條鏈
從單元素的根 出發,反覆把當前的根接到下一個單元素根之下。結果是一條鏈,其中 的深度為 。對數界的證明在此失效,因為包含 的樹每次都被接到更小的樹之下,所以每次深度增加時其大小並不翻倍。
常見錯誤
(支援合併,不支援刪除)
不相交集合結構支援合併,但不支援一般的刪邊。刪除一條已接受的圖的邊可能令一個連通分量分裂,僅憑這些父指標無法支援這種操作。Kruskal 算法中的用法是有效的,因為它只加入被接受的邊。
常見錯誤
(大小與秩是不同的量)
按大小合併與按秩合併是相關的策略,但它們所儲存的量含義不同。根的大小是當前集合的基數。在另一種實作中使用的秩,除非確實被維護為大小,否則不應稱為大小。
圖算法的代價
設圖有 個頂點和 條邊。對邊排序需要 次比較。初始化單元素集合需要 時間。 條邊中每條引起兩次查找和至多一次根連結,因此當 時,初等界給出額外的 時間。總時間為 ; 時的常數已被 的形式涵蓋。
對邊排序與不相交集合操作所做的是不同的工作。更快的合併並不能免去在此實作中對任意權排序的需要。反過來,如果邊已經排好序,這一輸入條件可以省去排序,但連通性操作及其正確性不變量仍然必不可少。
所儲存的資訊保證了甚麼
只有根的大小需要是最新的。當兩個根被連結時,子根處的舊大小可以留在記憶體中,但之後不得再把它當作某個獨立集合的大小。在合併比較大小之前,查找會沿父鏈走到當前的根。實作中可以為清晰起見清除舊值,但正確性取決於只在當前的根處查詢大小。
常見錯誤
(父指標並不是輸入的邊)
這片森林是對劃分的輔助表示,並不一定是輸入圖的子圖。父指標記錄的是哪個代表元被連結到另一個之下;它不必是引起該合併的圖的邊之一。因此父鏈不一定是原圖中的路徑。若要輸出最小生成森林,應單獨保存被接受的圖的邊。
例如,若一條被接受的邊連接頂點 和 ,實作連結的是它們所在兩個集合的根。這些根可能既不是 也不是 。合併仍然是正確的,因為這條圖的邊連接了兩個被表示的分量,而父指標只是記錄它們的合併。最小總權的證明涉及的是被接受的圖的邊,而不是父指標的任意方向。
總結
按大小合併迫使一個集合在其某個節點下降一層時至少翻倍,從而得到對數級的高度。不相交集合劃分追蹤被接受森林的分量,而割交換論證證明了 Kruskal 算法的最優性。路徑壓縮保持連通性,但其更強的攤還分析是另一個獨立的結果。
練習
快速檢查
(有八個單元素時,按大小合併定理所容許的最大深度是多少?)
對 計算 。
解答 · 答案
界為 。反覆合併大小相同的樹,並沿著被連到另一個根之下的那棵樹中的一片葉走,就可以達到這個界。
快速檢查
(為甚麼成功的合併會把新根處的大小更新為兩個舊大小之和?)
兩個根分別表示哪些集合?
解答 · 答案
兩個根所表示的集合互不相交。連結它們把這兩個集合合併,既不重複也不刪除元素,所以基數相加。若兩個元素的根相同,則沒有合併不同的集合,不可以把大小相加。
快速檢查
(在三角形的例子中,即使第三條邊的權重與第二條邊相同,為甚麼它仍被拒絕?)
比較它兩個端點的代表元。
解答 · 答案
接受前兩條邊之後,第三條邊的端點已經由被選中的路徑連通。加入第三條邊會產生圈。代表元相等就能檢測出這一點,與權重是否相同無關。
快速檢查
(經過一次帶路徑壓縮的查找之後,根所儲存的大小會怎樣?)
壓縮會增加或移除元素嗎?
解答 · 答案
保持不變。壓縮改變的是同一集合內的父指標,並沒有增加或移除元素。只有對不同集合的成功合併才會改變根所儲存的基數。
練習 3.8.9
(對合併次數作歸納,證明:在按大小合併且不作壓縮時,每棵高度為 的樹至少有 個節點。)
核心證明
樹的高度是其節點的最大深度。大小相同時,可以任意決定連結的方向。
提示(1)
連結兩棵樹時,新的高度是接收樹的高度與被連結樹的高度加一之中較大的一個。
解答(3)
- 1
檢查起始的樹
單元素樹的高度為 ,節點數為 。
依據: 每棵樹都從單元素開始。
- 2
把較小的樹 連到 的根之下
關鍵一步
設 的高度為 ,並且都滿足結論。連結後的樹 的高度為 ,且 。
依據: 按大小合併保證 。
- 3
分兩種情形討論高度
∎若 ,則 。若 ,則 。兩種情形都有 ,所以每次合併之後結論依然成立。