進階資料結構(2) Disjoint Sets 101北一女中 資訊選手培訓營 進階資料結構(2) Disjoint Sets 2012.08. 05 Nan
集合 Set
Disjoint Sets
儲存資料的方式 (1) Linked-list (2) Tree 用array模擬—記自己的parent!
支援的操作 建立一個Set 得到一個Set的root(代表) [Find] 問兩個元素是不是在同一個Set 合併兩個Sets [Union]
建立一個Set 把該Set的所有元素的parent都設成同一個元素A，把A的parent設成-1 通常Disjoint Set都是從所有元素 2 4 3 Id 1 2 3 4 parent -1 int set_r[N]; void init(){ for ( i = 0 ; i < N ; i++ ) set_r[i] = -1; } 通常Disjoint Set都是從所有元素 都是獨立的開始的都設成-1
得到一個Set的root(代表) 利用遞迴的方式不斷地向上詢問parent是誰 最後找到-1那個就是這個Set的root(代表)了 5 6 2 4 3 Id 1 2 3 4 5 6 parent -1
實作—遞迴 int set_r[N]; // 記錄每個元素的parent int findRoot(int idx){ if ( set_r[idx] == -1 ) // 如果parent已經是-1，代表該元素就是root return idx; return findRoot(set_r[idx]); // 如果不是的話就直接往上找自己parent }
Path壓縮技 因為每次都要遞迴上去，會花上一些時間，所以可以在遞迴時就順便把所有點的parent改成回傳的那個root(就等於是把樹壓平) 1 2 4 3 1 2 4 3 Id 1 2 3 4 parent -1 Id 1 2 3 4 parent -1
實作 int set_r[N]; // 記錄每個元素的parent int findRoot(int idx){ if ( set_r[idx] == -1 ) // 如果parent已經是-1，代表該元素就是root return idx; return (set_r[idx] = findRoot(set_r[idx])); // 回傳順便設給自己 p.s.指派時整個式子的值就是最後set_r[idx]的值 }
問兩個元素是不是在同一個Set 看他們的root是不是同一個，如果是就代表兩個元素在同一個Set，不是就是不是。 int set_r[N]; // 記錄每個元素的parent int inSameSet(int idxA, int idxB){ if ( findRoot(idxA) == findRoot(idxB) ) return 1; // 如果兩個root相同回傳1 (代表True) return 0; // 反之回傳0，代表False }
合併兩個Sets 把兩個set的其中一個root的parent 設成另外一個set的root
把6的root的parent設成2的root 1 2 4 3 5 6 Id 1 2 3 4 5 6 parent -1 合併2 & 6 找到2的root 1 (同時有做path壓縮) 找到6的root 5 把6的root的parent設成2的root 5 6 1 2 4 3 Id 1 2 3 4 5 6 parent -1
實作—遞迴 int set_r[N]; // 記錄每個元素的parent void unionSets(int idxA, int idxB){ if ( inSameSet(idxA, idxB) ) // 如果在同個Set就不需要合併 return; int rootA = findRoot(idxA); // 找到元素A的Root int rootB = findRoot(idxB); // 找到元素B的Root set_r[rootB] = rootA; // 把元素B的Root的parent改成元素A的Root }
看完影片你該知道的是… Disjoint Sets是什麼 Disjoint Sets如何使用陣列模擬樹狀結構 Disjoint Sets如何找到樹狀結構的Root Disjoint Sets如何在找Root時壓縮Path Disjoint Sets如何知道兩個元素是否屬於同個Set Disjoint Sets如何Union兩個Sets