Union-Find - HackMD

# Union-Find source: [Coursera Algorithms, Part 1](https://www.coursera.org/learn/algorithms-part1) Algorithms, 4th ed. - [Sedgewick, Wayne] --- ## 什麼是 Union-Find - 尋找一批 object 中的任兩個 object 是否在同一群 - 同一群的 object 間，有路可以找到彼此 - 路表示 object 之間的連結 - 兩個不同群的 object 間，找不到路可以通到對方 --- ## 為什麼要知道 Union-Find - 應用環境 - 圖片畫素 - 網路節點 - 社交軟體的朋友關係 - 電路晶體 - ... --- ## Union（連結）的建立 - 每個 object 都給一個編號 - 假設有 N 個 object ，編號從 0~N-1 - 用 connect(a, b) 表示連結編號 a 和編號 b - ex: connect(3, 10) 表示連結 object 3 和 object 10 --- ## 如何判斷在同一群 - 儲存連結的方式影響判斷的速度 - list - 有關係的 object 串在同一個list中 - 判斷兩個 object 是否在同一個list中 - array - 每個 object 都有一個標籤 - 判斷兩個 object 的標籤一不一樣 - array 比較快，因為只要比較一次 (quick-find) --- ## 如何用array儲存 - 建立 array - 標籤建立時使用對應 object 的編號 | object | 0 | 1 | 2 | ... | N-1 | |- |- |- |- |- |- | |標籤 | 0 | 1 | 2 | ... | N-1 | ---  ## 如何用array儲存 - 建立連結 - 連結在一起的 object 把標籤改成一樣 - 假設改成跟第二個 object 一樣 - connect(1,3) | object | 0 | 1 | 2 | 3 | |- |- |- |- |- | |標籤 | 0 | 3 | 2 | 3 | - connect(3,2) | object | 0 | 1 | 2 | 3 | |- |- |- |- |- | |標籤| 0 | 2 | 2 | 2 | --- ## 成本 - 讀寫 array 的次數 - 連結兩個 object 時就要把整個 array 走一次，才能確保該改的標籤都有改到 - 若是對 $N$ 個 object 做 $N$ 次連結，就需要 $N^2$ 次讀寫 - **Slow!** |方法|建立 |連結 |判斷 | |- |- |- |- | | quick-find | $N$ | $N$ | $1$ | --- ## 改進 - 連結成本 - 用樹狀的方式連結 (quick-union) - 標籤改成代表 parent object --- - object 標籤與 object 編號一樣時表示 object 是一個 root - 連結兩個 object 等於把兩個 object 所在的 tree 合併成一個 tree --- ## 樹狀 array - 建立 - 標籤建立時每個 object 就是一個 root | object | 0 | 1 | 2 | ... | N-1 | |- |- |- |- |- |- | |標籤 | 0 | 1 | 2 | ... | N-1 | ---  ## 樹狀 array - 連結 - 假設使用第二個 object 的 root 當作新的 root ---  - connect(1,3) | object | 0 | 1 | 2 | 3 | 4 | |- |- |- |- |- |- | |標籤 | 0 | 3 | 2 | 3 | 4 | - connect(0,4) | object | 0 | 1 | 2 | 3 | 4 | |- |- |- |- |- |- | |標籤 | 4 | 3 | 2 | 3 | 4 | ---  - connect(1,0) - object 1 root = object 3 - object 0 root = object 4 | object | 0 | 1 | 2 | 3 | 4 | |- |- |- |- |- |- | |標籤 | 4 | 3 | 2 | 4 | 4 | --- ## 成本 - 最差的情況下樹的深度可能跟 object 數量一樣 - unbalanced tree - 連結時找 root 的讀寫次數與深度有關 - 最多 $N$ 次 - 以 object root 是否相同判斷有沒有在同一群 - 也跟樹的深度相關 - 最多 $N$ 次 ---  - **Slow too!** |方法|建立 |連結 |判斷 | |- |- |- |- | | quick-find | $N$ | $N$ | $1$ | | quick-union| $N$ | $N$ | $N$ | --- ## 改進 - 避免樹長太深 - 紀錄樹的深度（weighted quick-union(QU)) - 連結時把矮的樹並到高的樹中 - 減緩樹變深的速度 ![](https://i.imgur.com/TKRcyLp.png) --- - 樹的深度最多是 $log_2N$ - 為什麼？ --- ## 原因 - 要讓 tree x 深度+1，tree x 就必須跟至少跟自己一樣長的 tree y 合併 - 深度每+1，樹包含的 object 數量就 double - $N$ 個 object 最多只能 double $log_2N$ 次 --- ## 成本 |方法|建立 |連結 |判斷 | |- |- |- |- | | quick-find | $N$ | $N$ | $1$ | | quick-union| $N$ | $N$ | $N$ | | weighted QU| $N$ | $log_2N$ | $log_2N$ | --- ## 改進 - 讓樹更扁 - 找 object 的 root 時，順手把所有經過的 object 都往上提兩層 (path compression) - 把 parent object 改成 grand parent object - 找到 root 後，原本 object 所在的深度就會減半 --- ## 成本 - 專家說會變成 $Nlog_2^*N$ - $log_2^*N$ = 對 $N$ 重複做 $log_2$ 到 $\leq1$ 的次數 ([Iterated logarithm](https://en.wikipedia.org/wiki/Iterated_logarithm)) - $log_2^*65536$ = 4 - $log_265536=16$, $log_216=4$, $log_24=2$, $log_22=1$ --- |方法|建立 |連結 |判斷 | |- |- |- |- | | quick-find | $N$ | $N$ | $1$ | | quick-union| $N$ | $N$ | $N$ | | weighted QU (WQU)| $N$ | $log_2N$ | $log_2N$ | | WQU & path compression| $N$ | $log_2^*N$ | $log_2^*N$ |