Data Structure for Disjoint Sets

Presentation on theme: "Data Structure for Disjoint Sets"— Presentation transcript:

1 Data Structure for Disjoint Sets

2 11.1 Disjoint-set 指令 Disjoint set 資料結構：
一個維護所有 disjoint dynamic sets 組成的大集合 S={S1, S2, …, Sk} 的資料結構。 每個集合都被一個 representative 所代表，而 representative 是該集合中的某一個元素。 舉例來說，在一個中學內有很多班級 我們可以說一個班級的學生就構成一個集合，而該班的班長則是該集合的代表人物 所以如果我們要知道某個學生位在那個班級內，只要問那個學生他們班的班長是誰即可 Disjoint Sets

3 此資料結構支援以下的指令： Make-Set(x): 創造一個新的集合 {x} Union(x, y): 把兩個分別包含 x, y 的集合聯集起來 Find-Set(x): 傳回一個指標指向包含 x 的集合的 representative。 註：在某些應用中，使用那一個元素當作 representative 並不會有影響，只要在每次變動之間，代表一個集合的 representative 皆是同一個元素即可。而在其它的應用中，必需依照特定的規則來選擇 representative，例如在集合中，選數字最小者當作 representative。 Disjoint Sets

4 m: 所有 Make-Set、Union 及 Find-Set 指令的總數。
符號： n: 所有 Make-Set 指令的總數。 m: 所有 Make-Set、Union 及 Find-Set 指令的總數。 註： m  n 且所有 Union 指令的總數最多不會超過 n-1。 如果所有Union指令的總數等於n-1的時候，全部的人都已經在同一個集合內了 接下來再做Union也沒有意義。 Disjoint Sets

5 disjoint-set 資料結構例子 a b e f h j c d g i (a) Disjoint Sets
(a,b)代表把包含a跟b的集合聯集起來 所以在第五個Union (a,b)執行之前，原本包含a的集合是 {a,c}，原本包含b的集合是 {b,d} Union(a,b)之後a,c,b,d都在同一個集合內了。 (a) 為 (b) 執行完之後的結果 (有edge相連代表在同一個集合內) Disjoint Sets

6 disjoint-set 資料結構例子 (續)
CONNECTED-COMPONENTS(G) 1 for each vertex v  V[G] 2 do MAKE-SET(v) 3 for each edge (u,v)  E[G] 4 do if FIND-SET(u) ≠ FIND-SET(v) then UNION(u,v) 1.2 行的意義是一開始將每個點單獨看成不同的集合 第三行之後則是對於每一條edge(u,v)，假設u,v在不同的集合之內，就將包含他們的集合聯集起來 最後看剩下幾個集合，就是有幾個connected component。 Disjoint Sets

7 disjoint-set 資料結構例子 (續)
SAME-COMPONENT(u,v) 1 if FIND-SET(u) = FIND-SET(v) 2 then return TRUE 3 else return FALSE 要知道兩個元素是否在相同的集合之內，只要看他們所在集合的代表人物是否相同即可 Disjoint Sets

8 11.2 Linked-list 表示法 以序列中第一個元素當作 representative。
head c h e b / tail head f g d / Make-Set以及Find-Set很快，因為只要跨一步就可以知道該集合的代表人物是誰 但是Union就很慢了(見下頁範例) tail 以序列中第一個元素當作 representative。 Make-Set, Find-Set: 耗時 O(1)。 Disjoint Sets

9 簡單的 Union(x, y) 作法 把第一個序列串接在第二個之後。 f g d c h e b / head tail
The first list: c->h->e->b The second list: f->g->d Append the second onto the first: d.next->c c.prev->f h.prev->f e.prev->f b.prev->f Time is proportional to the length of the first list. Disjoint Sets

10 每個指令的 amortized time 為 O(n)。 O(n)
m = 2n-1 個指令耗時 O(n2) 每個指令的 amortized time 為 O(n)。 Operation Number of objects updated MAKE-SET(x1) 1 MAKE-SET(x2) 1 MAKE-SET(xn) 1 UNION(x1, x2) 1 UNION(x2, x3) 2 UNION(x3, x4) 3 UNION(xn-1, xn) n-1 O(n) O( n) =O(n2) n times Make-Set: O(n) n-1 times Union: O(1+2+3+…+n-1) = O(n2) 效率不好 Disjoint Sets

11 A weighted-union heuristic
每一個 representative 存放其代表的序列的長度。 把較短的序列附加在較長的序列之後。 如前例，有兩個集合{f, g, d} 以及 {c, h, e, b} 聯集的時候應該將 {f, g, d} 放到 {c, h, e, b} 之後。 Disjoint Sets

12 Theorem 1: 使用 weighted-union heuristic 後，假設 Make-Set 指令總數為 n 個，則 m 個連續的 Make-Set, Union, 與 Find-Set 指令耗時 O(m+nlg n) Disjoint Sets

13 證明 Theorem 1 執行 Make-Set(x) 後，x 所在的序列中只包含 x 一個元素。
在 x 的 representative pointer 執行第一次更新之後，x 所在的序列中包含了至少兩個元素。 Disjoint Sets

14 證明 Theorem 11.1 (續) 接下來我們可以觀察到在對 x 的 representative 執第 k 次更新後，包含 x 的序列至少有 2k 個元素。 由於 k=O(lg n)，所有 Union 指令所耗的時間最多為 O(nlg n)。 每個 Make-Set 及 Find-Set 指令皆耗時 O(1)。因此證明成立。 Disjoint Sets

15 11.3 Disjoint-set forests Tree 的 root 為 representative。
c f f h e d c d b g h e g b Tree 的 root 為 representative。 Make-Set(x): 耗時 O(1) Find-Set(x): 耗時 O(h)，h 為包含 x 的 tree 的高度。 (找 x  root 的路徑) Union(x, y): x 的 root 指向 y 的 root。  耗時 O(h)。 In the Union of x and y, we have to perform Find-Set(x) and Find-Set(y). Disjoint Sets

16 Union by rank: 由較小的 tree 的 root 指向較大的 tree 的 root (依照 tree 的高度區分)。
一些增進執行速度的技巧 Union by rank: 由較小的 tree 的 root 指向較大的 tree 的 root (依照 tree 的高度區分)。 rank[x]: x 的高度(由 x 到一 descendant leaf 的最長路徑的邊的數量) Path compression: 在執行 Find-Set(x) 對過程中，把所有find path 上的點指向 root。(不改變任何 rank 的值) Disjoint Sets

17 範例: Find-Set(a) with Path Compression
b c d e c Path Compression: make each node on the ‘find path’ point to the root (Find path: a  root) root為 f, 我們要找 a 所在集合的代表人物是誰，必須經過b, c, d, e, 最後才到 root f， 但是經過這次的動作之後，我們就直接把a, b, c, d, e 接到root f, 變成右邊的樣子， 雖然這次花了O(h)的時間才知道答案， 但是下次再問 a 所在集合的代表人物是誰，只需要跨一步就知道了。 b a Disjoint Sets

18 Pseudo-code for disjoint-set forests
MAKE-SET(x) 1 p[x]  x 2 rank[x]  0 UNION(x,y) 1 LINK(FIND-SET(x), FIND-SET(y)) path compression Disjoint Sets

19 union by rank LINK(x,y) 1 if rank[x] > rank[y] 2 then p[y]  x
3 else p[x]  y if rank[x] = rank[y] then rank[y]  rank[y] + 1 FIND-SET(x) 1 if x ≠ p[x] 2 then p[x]  FIND-SET(p[x]) 3 return p[x] union by rank Link的時候做Union by Rank Find-Set的時候做Path Compression (紅色部分的recursive call) Disjoint Sets

20 Effect of the heuristics on the running time
若只使用了 Union-by-rank， 簡單便可證明總共耗時 O(mlg n)。 若只使用了 Path-compression 可以證明 (在此不證) 總耗時為 Θ(n + f ‧ (1+log2+f/nn))， 其中 n 是 Make-Set 指令的數量，且 f 是 Find-Set 指令的數量。 Disjoint Sets

21 當兩者皆用上時，在最壞的情況下共需耗時 O(m(m,n))。
註： (m,n) 是 Ackermann’s function 的反函數，其成長速率非常慢。在所有可能的應用中，(m,n)  4，因此在所有實際的應用上，我們可以把執行時間視為和 m 成正比。  接下來定義完 Ackermann’s function 會介紹到。 Disjoint Sets

22 Ackermann’s function and its inverse
令 g(i) = 為 repeated exponentiation。 (即 g(4) = ) 函數 lg* n = min{i0: lg(i) n  1} 本質上為 g(i) 的反函數 (即 lg* = 5) 註： lg*g(i)=i+1。 g(0)=2, g(1)=22, g(2)=2^(22) lg*(g(i)) = i+1 Disjoint Sets

23 The Ackermann’s function: 對整數 i, j  1， A(1, j) = 2j for j  1
A(i, 1) = A(i-1, 2) for i  2 A(i, j) = A(i-1, A(i, j-1)) for i, j  2 Disjoint Sets

24 因對所有的 j  1，A(2, j) = = g(j) 所以當 i  2，A(i, j)  g(j)。
Ackermann’s function 的反函數: (m, n) = min{i1: A(i, m/n)>lg n}。 A(4, 1) = A(3, 2) = g(16) ≈ 1080 Disjoint Sets

25 由於當 i2，A(i, j)  g(j)，因此 (m, n) = O(lg* n)。 註：
由於 lg n < 1080，且 A(4, m/n)  A(4, 1)  1080，我們得知在實際應用上，(m, n)  4。 在實際應用上，lg* n5 (n265536)。 由於當 i2，A(i, j)  g(j)，因此 (m, n) = O(lg* n)。 註： 1, , lg*, lglg, lg, n1/2, n, nk, 2n, g, A 大小關係:  < lg*n < lglgn < lgn < n, … increasing Disjoint Sets

26 Exercises Problem 1: 有一個城鎮住了 N 個居民。其中我們知道在這些居民當中，有一些成對的好朋友。根據名言“我朋友的朋友也是我的朋友”，我們可以知道如果 A 和 B 是朋友，B 和 C 是朋友，那麼 A 和 C 也是朋友。你的工作就是要算出在這個城鎮內最多有幾個人互相為朋友。 輸入：第一行包含兩個整數 N, M，其中 N 代表城鎮內的居民數(1N30000)，M 代表我們知道互為朋友的對數(0M500000)。接下來的 M 行，每一行都有兩個整數 A 與 B (1≤A≤N, 1≤B≤N, A≠B)，代表 A 和 B 是朋友。這些成對的朋友可能會有重複。 輸出：輸出只有一個數字，表示最大的一群朋友們是由幾個人構成。 Disjoint Sets

27 以下是一個輸出入的實例: Sample Input Sample Output 2 3 2 1 2 2 3 10 12 3 1 3 4
5 4 3 5 4 6 5 2 2 1 7 10 9 10 8 9 3 6 Disjoint Sets

28 Exercises Problem 2: 鮑伯是一個網管，負責管理一堆網路連線的電腦。他要紀錄在這網路中電腦連線的情況。每個連線都是雙向的，且兩台電腦可以直些相連，或是間接透過其他電腦來互相溝通。然而，鮑伯有時候必須要根據自己的紀錄很快地知道某兩台電腦是否有相連（不管直接或間接）。請寫一個程式來幫助鮑伯，鮑伯會給你兩台電腦的編號，你只需要檢查是否那兩台電腦有連線。 Disjoint Sets

29 Exercises 輸入：第一行是一個正整數 n (n < 1000)，接下來的數行內會有以下兩種格式：
(a) c compi compj，代表鮑伯將第 i 台電腦與第 j 台 電腦直接相連 (b) q compi compj，代表鮑伯想知道第 i 台電腦與第 j 台電腦是否有連線（不論直接或間接） 電腦的編號是從 0 到 n-1，每一行只會有 (a) 或 (b)。 輸出：輸出只有兩個數字，第一個數字表示在鮑伯的問題中有幾個答案是肯定的，第二個數字則是否定的數目。兩個數字中間用一個逗號隔開。 Disjoint Sets

30 以下是一個輸出入的實例: Sample Input Sample Output 10 c 1 5 c 2 7 q 7 1 c 3 9
1,2 Disjoint Sets

31 Exercises Problem 3: A 和 B 兩個國家在戰爭中，身為 C 國的國民，你決定要幫助你的國家在參加和平會談的時候從事間諜活動。除了你之外，在這個會談中總共有 n 個人，但是你不知道他們分別代表哪個國家。你可以從他們一對一的談話中知道那兩個人是朋友還是敵人。事實上你的國家想要知道的是某些人是否來自同一個國家，或者他們是敵人。在和平會談當中，你會接到 C 國政府的指令，然後你必須根據到目前為止的觀察來回報。很幸運地，沒有人和你交談，也沒人注意到你不起眼的容貌。 Disjoint Sets

32 Exercises 正式地說，考慮以下的指令：
setFriends(x,y): 表示 x 與 y 是來自同一個國家 setEnemies(x,y): 表示 x 與 y 是來自不同國家的敵人 areFriends(x,y): 要回報是否 x 與 y 為同一個國家的朋友 areEnemies(x,y): 要回報是否 x 與 y 為不同國家的敵人 前兩個指令如果跟你先前得到的資訊矛盾，則必須要發出錯誤訊息。朋友(用~表示)以及敵人(用*表示)這兩個關係有以下的特性： 1. If x~y and y~z then x~z (我朋友的朋友也是我的朋友) 2. If x~y then y~x (朋友的關係是互相的) 3. x~x (每個人都是自己的朋友) 4. If x*y then y*x (憎恨是互相的) 5. Not x*x (沒有人是自己的敵人) 6. If x*y and y*z then x~z (一個共同的敵人讓兩個人變成朋友) 7. If x~y and y*z then x*z (我朋友的敵人也是我的敵人) Disjoint Sets

33 Exercises 指令 setFriends(x,y) 和 setEnemies(x,y) 必須要維持上述的特性。
輸入：第一行包含一個整數 n (n < 10000)，代表參加會談的人數。接下來的數行，每一行都會有三個整數 c x y，其中 c 是指令的編號： c=1, setFriends c=2, setEnemies c=3, areFriends c=4, areEnemies x 和 y 就是該指令的參數，範圍是 [0,n)，表示兩個不同的人。最後一行會是 0 0 0。 輸入檔的所有整數都會用空白或是換行字元隔開。 Disjoint Sets

34 Exercises 輸出：對於每個 areFriends 以及 areEnemies 指令，印出 0 (代表否定的答案)或是 1 (代表肯定的答案)。對於 setFriends 以及 setEnemies 指令，如果與先前的資訊矛盾，要輸出–1，請注意與先前資訊矛盾的指令要忽略。一個成功的 setFriends 或是 setEnemies 不用輸出任何東西。 Disjoint Sets

35 以下是一個輸出入的實例: Sample Input Sample Output 10 1 0 1 1 1 2 2 0 5 3 0 2
3 8 9 4 1 5 4 1 2 4 8 9 1 8 9 1 5 2 3 5 2 0 0 0 1 -1 Disjoint Sets