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

1、不相交集合的操作

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

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

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

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

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

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

確定無向圖的連通分量

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

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

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

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

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

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

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

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

2.1 合并的一個簡單實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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、不相交集合森林

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

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

3.1 改進運行時間的啟發(fā)式策略

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

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

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

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

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

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

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

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é)點的父結(jié)點 為根結(jié)點
3   return x.p

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

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

3.3 啟發(fā)式策略對運行時間的影響

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

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

當(dāng)同時使用 按秩合并與路徑壓縮時，最壞情況下的運行時間為 O(mα(n))，這里 α(n) 是一個增長非常慢的函數(shù)，在任何一個 可以想到的 不相交集合數(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（帶路徑壓縮）改為非遞歸版本。

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

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