一些應(yīng)用涉及 將n個(gè)不同的元素分成一組不相交的集合。尋找包含給定元素的唯一集合 和 合并兩個(gè)集合

1、不相交集合的操作

1、一個(gè)不相交集合 數(shù)據(jù)結(jié)構(gòu) 維持了 一個(gè)不相交動(dòng)態(tài)集的集合 S = {S_1, S_2,…, S_n}。用一個(gè)代表 來標(biāo)識(shí)每個(gè)集合，它是這個(gè)集合的某個(gè)成員。在一些應(yīng)用中，不關(guān)心 哪個(gè)成員被用來作為代表，僅僅關(guān)心的是 重復(fù)兩次查詢動(dòng)態(tài)集合的代表中，如果 這兩次查詢 沒有修改動(dòng)態(tài)集合，則兩次查詢 應(yīng)該得到相同的結(jié)果。其他一些應(yīng)用 可能會(huì)需要一個(gè)預(yù)先說好的規(guī)則 來選擇代表，比如 選擇這個(gè)集合中最小的成員

2、用一個(gè)對(duì)象 表示一個(gè)集合的每個(gè)元素。設(shè) x 表示一個(gè)對(duì)象，希望支持以下三個(gè)操作：

1. MAKE-SET(x): 建立 一個(gè)新的集合，它的唯一成員 (因而為代表) 是 x。因?yàn)楦鱾€(gè)集合是不相交的，故 x 不會(huì)出現(xiàn)在 別的某個(gè)集合中
2. UNION(x, y): 將包含 x 和 y 的兩個(gè)動(dòng)態(tài)集合 (分別表示為S_x和S_y) 合成一個(gè)新的集合，即這兩個(gè)集合的并集。雖然 UNION 的很多實(shí)現(xiàn)中 特別地選擇 S_x 或 S_y 的代表作為新的代表，然而結(jié)果集的代表 可以是S_x∪S_y 的任何成員。由于 要求各個(gè)集合不相交，故要 “消除” 原有的集合 S_x 和 S_y，即 將它們從 S 中刪除。實(shí)際上，經(jīng)常把 其中一個(gè)集合的元素 并入另一個(gè)集合中，來代替刪除操作
3. FIND-SET(x): 返回一個(gè)指針，這個(gè)指針 指向包含 x 的(唯一)集合的代表

使用兩個(gè)參數(shù) 來分析 不相交集合數(shù)據(jù)結(jié)構(gòu)的運(yùn)行時(shí)間: 一個(gè)參數(shù)是 n，表示 MAKES-SET 操作的次數(shù)；另一個(gè)是m，表示 MAKE-SET、UNION 和 FIND-SET 操作的總次數(shù)

每個(gè) UNION 操作減少一個(gè)集合，因此，n - 1 次 UNION 操作后，只有一個(gè)集合留了下來。也就是說，UNION 操作的次數(shù) 至多是 n - 1。由于 MAKE-SET 操作 被包含在總操作次數(shù) m 中，因此有 m ≥ n。假定 n 個(gè) MAKE-SET 操作總是最先執(zhí)行

1.1 不相交集合數(shù)據(jù)結(jié)構(gòu)的一個(gè)應(yīng)用

確定無向圖的連通分量

下面的 CONNECTED-COMPONENTS 過程使用 不相交集合操作 計(jì)算一個(gè)圖的連通分量。一旦 SAME-COMPONENTS 預(yù)處理了該圖，過程 SAME-COMPONENT 就回答兩個(gè)頂點(diǎn)是否在 同一個(gè)連通分量的詢問（圖G的頂點(diǎn)集用 G.V 表示，邊集用 G.E 表示）

圖21-1(b)展示了 CONNECTED-COMPONENTS 如何計(jì)算不相交集合

CONNECTED-COMPONENTS(G)
1 for each vertex v ∈ G.V
2 	MAKE-SET(v)
3 for each edge (u, v) ∈ G.E
4 	if FIND-SET(u) ≠ FIND-SET(v)
5 		UNION(u, v)SAME-COMPONENT(u,v)
1 if FIND-SET(u) == FIND-SET(v)
2 	return TRUE
3 else return FALSE

處理完所有的邊之后，兩個(gè)頂點(diǎn)在相同的連通分量 當(dāng)且僅當(dāng) 與之對(duì)應(yīng)的對(duì)象在相同的集合中
一個(gè)表示頂點(diǎn)的對(duì)象會(huì)包含一個(gè)指向與之對(duì)應(yīng)的不相交集合對(duì)象的指針

2、不相交集合的鏈表表示

實(shí)現(xiàn) 不相交集合數(shù)據(jù)結(jié)構(gòu) 的簡單方法：每個(gè)集合 用一個(gè)自己的鏈表來表示。每個(gè)集合的對(duì)象 包含 head 屬性和 tail 屬性；head 屬性 指向鏈表的第一個(gè)對(duì)象，tail 屬性 指向鏈表的最后一個(gè)對(duì)象。鏈表中的每個(gè)對(duì)象 都包含一個(gè)集合成員，一個(gè)指向鏈表中 下一個(gè)對(duì)象的指針 和 一個(gè)指回到集合對(duì)象的指針。在每個(gè)鏈表中，對(duì)象可以 以任意的次序出現(xiàn)。代表是 鏈表中第一個(gè)對(duì)象的集合成員

MAKE-SET 操作 和 FIND-SET 操作 是非常方便的，只需 O(1) 的時(shí)間

要執(zhí)行 MAKE-SET(x) 操作，需要?jiǎng)?chuàng)建一個(gè) 只有 x 對(duì)象的新鏈表。對(duì)于 FIND-SET(x)，僅沿著指針 x 對(duì)象的返回指針 返回到集合對(duì)象，然后返回 head 指向?qū)ο蟮某蓡T

2.1 合并的一個(gè)簡單實(shí)現(xiàn)

UNION 操作 通過把 y 所在的鏈表 拼接到 x 所在的鏈表 實(shí)現(xiàn)了 UNION (x, y)。x 所在的鏈表的代表 成為結(jié)果集的代表。利用 x 所在鏈表的 tail 指針，可以迅速地找到 拼接 y 所在的鏈表的位置

對(duì)于 y 所在鏈表的每個(gè)對(duì)象，必須更新 指向集合對(duì)象的指針，這將花費(fèi)的時(shí)間 與 y 所在鏈表長度 呈線性關(guān)系

構(gòu)建一個(gè)在 n 個(gè)對(duì)象上需要 Θ(n²) 時(shí)間的 m 個(gè)操作序列。假設(shè) 有對(duì)象 x1, x2, …, xm，執(zhí)行 n 個(gè) MAKE-SET 操作，后面跟著 n-1 個(gè) UNION 操作。因而有 m = 2n - 1。執(zhí)行 n 個(gè) MAKE-SET 操作 需要 Θ(n) 時(shí)間。由于第 i 個(gè) UNION 操作更新 i 個(gè)對(duì)象（參數(shù)中 右側(cè) 插在 左側(cè)的集合后面）

因此所有的 n-1 個(gè) UNION 操作更新的對(duì)象的總數(shù)為：

總的操作數(shù)為 2n-1，這樣每個(gè)操作 平均需要 Θ(n) 的時(shí)間。也就是說，一個(gè)操作的攤還時(shí)間為 Θ(n)

2.2 一種加權(quán)合并的啟發(fā)式策略

1、在最壞情況下，上面給出的 UNION 過程的每次調(diào)用 平均需要 Θ(n) 的時(shí)間，這是因?yàn)?需要把一個(gè)較長的表 接到 一個(gè)較短的表上，此時(shí) 必須對(duì)較長表的每個(gè)成員 更新其指向集合對(duì)象的指針

加權(quán)合并啟發(fā)式策略：假使 表中包含了 表的長度（易于維護(hù)）以及 拼接次序 可以任意的話，總是 把較短的鏈表 拼接到較長的表中

2、使用不相交集合的鏈表表示 加權(quán)合并啟發(fā)式策略，一個(gè)具有 m 個(gè) MAKE-SET, UNION 和 FIND-SET 操作的序列（其中有 n 個(gè)是 MAKE-SET 操作）需要的時(shí)間為 O(m + nlg n)

證明：由于每個(gè)UNION操作 合并兩個(gè)不相交集，因此總共至多執(zhí)行 n-1 個(gè)UNION操作。現(xiàn)在來確定 由這些 UNION 操作所花費(fèi)時(shí)間的上界。首先 確定每個(gè)對(duì)象指向它的集合對(duì)象的指針 被更新次數(shù)的上界。每次 x 的指針被更新，x 一定先在一個(gè)規(guī)模較小的集合中。因此，第一次 x 的指針被更新時(shí)，結(jié)果集 一定至少有 2 個(gè)成員，類似地，下次 x 的指針 被更新時(shí) 結(jié)果集至少有4個(gè)成員。一直繼續(xù)下去，注意到 對(duì)于任意的 k ≤ n，在 x 的指針被更新 ?lg k? 次后，結(jié)果集 一定至少有 k 個(gè)成員。因?yàn)?最大集合 至多包含 n 個(gè)成員，所以 每個(gè)對(duì)象的指針在所有的 UNION 操作中最多被更新 ?lg n? 次。當(dāng)然，也必須考慮 tail 指針 和 表長度的更新，而它們?cè)诿總€(gè) UNION 操作中只花費(fèi) Θ(1) 時(shí)間。所以 總共花在 UNION 操作上的時(shí)間為 O(nlg n)

每個(gè) MAKE-SET 和 FIND-SET 操作需要 O(1) 時(shí)間，它們的總數(shù)為 O(m)。所以整個(gè)序列的總時(shí)間是 O(m+nlg n)

3、使用鏈表表示 和 加權(quán)合并啟發(fā)式策略，寫出 MAKE-SET、FIND-SET 和 UNION 操作的偽代碼，并指定 在集合對(duì)象和表對(duì)象中所使用的屬性

MAKE-SET(x)
// Assume x is a pointer to a node contains .key .set .nextCreate a node S contains .head .tail .sizex.set = Sx.next = NILS.head = xS.tail = xS.size = 1return S

FIND-SET(x)return x.set.head

UNION(x, y)S1 = x.setS2 = y.setif S1.size >= S2.sizeS1.tail.next = S2.headz = S2.headwhile z != NIL // 把S2中所有元素都改成S1的z.set = S1z = z.nextS1.tail = S2.tailS1.size = S1.size + S2.size // Update the size of setreturn S1elsesame procedure as abovechange x to ychange S1 to S2

3、不相交集合森林

在一個(gè) 不相交集合 更快的實(shí)現(xiàn)中，使用有根樹 來表示集合，樹中的每個(gè)節(jié)點(diǎn) 包含一個(gè)成員，每棵樹 代表一個(gè)集合。在一個(gè) 不相交集合森林中（如圖所示），每個(gè)成員僅指向它的父結(jié)點(diǎn)，每棵樹的根節(jié)點(diǎn) 包含集合的代表。每個(gè)樹中的每個(gè)成員都是它所在集合的成員，同時(shí)其根節(jié)點(diǎn)表示該集合的代表，并且是指向代表的根節(jié)點(diǎn)。我們可以在樹根節(jié)點(diǎn)中做任何操作來執(zhí)行FIND-SET，雖然樹根節(jié)點(diǎn)可能處于集合森林的不同位置，但是結(jié)果總是同樣的成員代表。隨著進(jìn)一步的優(yōu)化和策略“按秩合并”（union by rank），我們能得到一個(gè)漸近更優(yōu)的不相交集合數(shù)據(jù)結(jié)構(gòu)

MAKE-SET 操作 簡單地創(chuàng)建一棵 只有一個(gè)結(jié)點(diǎn)的樹，FIND-SET 操作 通過沿著指向父結(jié)點(diǎn)的指針 找到樹的根。這一通向 根結(jié)點(diǎn)的簡單路徑上所訪問的結(jié)點(diǎn) 構(gòu)成了 查找路徑。UNION 操作 使得一棵樹的根 指向另外一棵樹的根

3.1 改進(jìn)運(yùn)行時(shí)間的啟發(fā)式策略

第一種啟發(fā)式策略是 按秩合并，它類似于 鏈表表示中 使用的 加權(quán)合并啟發(fā)式策略。使具有較少節(jié)點(diǎn)的樹的根 指向具有較多的樹的根。不顯式地記錄 每個(gè)結(jié)點(diǎn)為根的子樹的大小，而是采用 一種易于分析的方法。對(duì)于每個(gè)結(jié)點(diǎn)，維護(hù)一個(gè)秩，該秩表示 該結(jié)點(diǎn)高度的一上界。使用按秩合并策略的 UNION 操作中，可以讓 具有較小秩的根指向具有較大秩的根

第二種啟發(fā)式策略是 路徑壓縮，在 FIND-SET 操作中，使用這種策略 可以使查找路徑中的每個(gè)結(jié)點(diǎn) 直接指向根。路徑壓縮 并不改變?nèi)魏谓Y(jié)點(diǎn)的秩

注意三角形是一棵樹，而不是 結(jié)點(diǎn)

3.2 實(shí)現(xiàn)不相交集合森林的偽代碼

為了使用 按秩合并的啟發(fā)式策略 實(shí)現(xiàn)一個(gè)不相交集合森林，必須記錄下 秩 的變化情況。對(duì)于每個(gè)結(jié)點(diǎn) x，維護(hù)一個(gè)整數(shù)值 x.rank，它代表 x 的高度 (從 x 到某一后代葉結(jié)點(diǎn)的 最長簡單路徑上 邊的數(shù)量) 的一個(gè)上界。當(dāng) MAKE-SET 創(chuàng)建 一個(gè)單元素集合時(shí)，這個(gè)樹上的單結(jié)點(diǎn) 有一個(gè)為0的初始秩。每一個(gè) FIND-SET 操作 不改變?nèi)魏沃?/p>

UNION 操作有 兩種情況，取決于 兩棵樹的根是否有相同的秩。如果 根沒有相同的秩，就 讓較大秩的根 成為較小秩的根的父結(jié)點(diǎn)（因?yàn)?FIND-SET 復(fù)雜度是高度），但秩本身保持不變。另一種情況是 兩個(gè)根有相同的秩時(shí)，任意選擇兩個(gè)根中的一個(gè) 作為父結(jié)點(diǎn)，并使它的秩加1

用 x.p 代表結(jié)點(diǎn) x 的父結(jié)點(diǎn)

MAKESET(x)
1	x.p = x
2	x.rank = 0UNION(x, y)
1   LINK(FIND-SET(x), FIND-SET(y))LINK(x, y)
1   if x.rank > y.rank
2      y.p = x
3   else x.p = y
4      if x.rank == y.rank
5         y.rank = y.rank + 1

帶有路徑壓縮的 FIND-SET 過程

FIND-SET(x)
1   if x != x.p
2      x.p = FIND-SET(x.p) // 使 x 到根路徑上的所有結(jié)點(diǎn)的父結(jié)點(diǎn) 為根結(jié)點(diǎn)
3   return x.p

FIND-SET 過程是一種兩趟方法：當(dāng)它遞歸時(shí)，第一趟 沿著查找路徑向上 直到找到根，當(dāng)遞歸回溯時(shí)，第二趟沿著搜索樹向下 更新到 結(jié)點(diǎn) x 路徑中的每個(gè)結(jié)點(diǎn)，使其直接指向根。FIND-SET(x) 的每次調(diào)用 在第3行返回 x.p

如果 x 是根，那么 FIND-SET 跳過第2行并返回 x.p，也就是x，這是遞歸到原點(diǎn)的情形。否則，第2行執(zhí)行，并且參數(shù)為 x.p 的遞歸調(diào)用 返回一個(gè)指向根的指針。第2行 更新結(jié)點(diǎn) x 并讓其直接指向根結(jié)點(diǎn)，然后第3行 返回這個(gè)指針

3.3 啟發(fā)式策略對(duì)運(yùn)行時(shí)間的影響

單獨(dú)使用按秩合并 或 路徑壓縮，每個(gè)都能改善 不相交集合森林上 操作的運(yùn)行時(shí)間，而兩者結(jié)合在一起 效果更好。單獨(dú)來看，路徑壓縮產(chǎn)生的運(yùn)行時(shí)間上限為 O(m lg n)，并且這是個(gè)界是緊確的

對(duì)于一個(gè)具有 n 個(gè) MAKE-SET 操作（因此最多有 n-1 個(gè)UNION操作）和 f 個(gè) FIND-SET 操作的操作序列，單獨(dú)使用 路徑壓縮啟發(fā)式策略的 最壞情況下的 運(yùn)行時(shí)間為 Θ(n+ f*(1 + log(2+f/n)n))

當(dāng)同時(shí)使用 按秩合并與路徑壓縮時(shí)，最壞情況下的運(yùn)行時(shí)間為 O(mα(n))，這里 α(n) 是一個(gè)增長非常慢的函數(shù)，在任何一個(gè) 可以想到的 不相交集合數(shù)據(jù)結(jié)構(gòu)的應(yīng)用中，α(n) 都 ≤ 4

21.3-1 用按秩合并 與 路徑壓縮啟發(fā)式策略 的不相交集合森林 完成

1 for i = 1 to 16
2 	MAKE-SET(x_i)
3 for i = 1 to 15 by 2
4 	UNION(x_i, x_{i+1})
5 for i = 1 to 13 by 4
6 	UNION(x_i, x_{i+2})
7 UNION(x_1, x_5)
8 UNION(x_9, x_13)
9 UNION(x_1, x_9)

假定如果集合x_i 和x_j 的集合有相同的大小，則 UNION(x_i, x_j) 表示將x_j 所在的表鏈接到x_i 所在的表后

21.3-2 將遞歸版本的 FIND-SET（帶路徑壓縮）改為非遞歸版本。

為了實(shí)現(xiàn)非遞歸的 FIND-SET，假設(shè)我們?cè)谠?x 上調(diào)用該函數(shù)。創(chuàng)建一個(gè)鏈表 A，其中包含指向 x 的指針。每次我們 向樹的上層移動(dòng)一個(gè)元素時(shí)，將指向該元素的指針 插入鏈表 A 中。一旦找到根節(jié)點(diǎn) r，使用該鏈表找到從根節(jié)點(diǎn)到 x 的路徑上的每個(gè)節(jié)點(diǎn)，并將這些節(jié)點(diǎn)的父節(jié)點(diǎn)更新為 r

21.3-3 給出一個(gè)包含n個(gè) MAKE-SET、UNION 和 FIND-SET 操作的序列（其中有 n 個(gè)是 MAKE-SET 操作)，當(dāng)僅使用按秩合并時(shí)，需要 Ω(m lg n) 的時(shí)間