Data Structure for Disjoint Sets.ppt

Disjoint Sets Data Structure for Disjoint Sets 11.1 Disjoint-set 指令 Disjoint set 資料結構： 一個維護所有 disjoint dynamic sets 組成的大集合 S={S1, S2, …, Sk} 的資料結構。 每個集合都被一個 representative 所代表，而 representative 是該集合中的某一個元素。 此資料結構支援以下的指令： Make-Set(x): 創造一個新的集合 {x} Union(x, y): 把兩個分別包含 x, y 的集合聯集起來 Find-Set(x): 傳回一個指標指向包含 x 的集合的 representative。 註：在某些應用中，使用那一個元素當作 representative 並不會有影響，只要在每次變動之間，代表一個集合的 representative 皆是同一個元素即可。而在其它的應用中，必需依照特定的規則來選擇 representative，例如在集合中，選數字最小者當作 representative。 符號： n: 所有 Make-Set 指令的總數。 m: 所有 Make-Set、Union 及 Find-Set 指令的總數。 註： m ? n 且所有 Union 指令的總數最多不會超過 n-1。 disjoint-set 資料結構例子 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) 5 then UNION(u,v) disjoint-set 資料結構例子 (續) SAME-COMPONENT(u,v) 1 if FIND-SET(u) = FIND-SET(v) 2 then return TRUE 3 else return FALSE 11.2 Linked-list 表示法 簡單的 Union(x, y) 作法 把第一個序列串接在第二個之後。 m = 2n-1 個指令耗時 O(n2) 每個指令的 amortized time 為 O(n)。 A weighted-union heuristic 每一個 representative 存放其代表的序列的長度。 把較短的序列附加在較長的序列之後。 Theorem 1: 使用 weighted-union heuristic 後，假設 Make-Set 指令總數為 n 個，則 m 個連續的 Make-Set, Union, 與 Find-Set 指令耗時 O(m+nlg n) 證明 Theorem 1 執行 Make-Set(x) 後，x 所在的序列中只包含 x 一個元素。 在 x 的 representative pointer 執行第一次更新之後，x 所在的序列中包含了至少兩個元素。 證明 Theorem 11.1 (續) 接下來我們可以觀察到在對 x 的 representative 執第 k 次更新後，包含 x 的序列至少有 2k 個元素。 由於 k=O(lg n)，所有 Union 指令所耗的時間最多為 O(nlg n)。 每個 Make-Set 及 Find-Set 指令皆耗時 O(1)。因此證明成立。 11.3 Disjoint-set forests 一些增進執行速度的技巧 Union by rank: 由較小的 tree 的 root 指向較大的 tree 的 root (依照 tree 的高度區分)。 rank[x]: x 的高度(由 x 到一 descendant leaf 的最長路徑的邊的數量) Path compression: 在執行 Find-Set(x) 對過程中，把所有find path 上的點指向 root。(不改變任何 rank 的值) 範例: Find-Set(a) with Path Compression 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)) LINK(x,y) 1 if rank[x] rank[y] 2 then p[y] ? x 3 else p[x] ? y 4 if rank[x]