什麼是 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 |
0 |
1 |
2 |
… |
N-1 |
標籤 |
0 |
1 |
2 |
… |
N-1 |
如何用array儲存 - 建立連結
-
連結在一起的 object 把標籤改成一樣
-
connect(1,3)
object |
0 |
1 |
2 |
3 |
標籤 |
0 |
3 |
2 |
3 |
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 |
0 |
1 |
2 |
… |
N-1 |
標籤 |
0 |
1 |
2 |
… |
N-1 |
樹狀 array - 連結
- 假設使用第二個 object 的 root 當作新的 root
object |
0 |
1 |
2 |
3 |
4 |
標籤 |
0 |
3 |
2 |
3 |
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 數量一樣
- 連結時找 root 的讀寫次數與深度有關
- 以 object root 是否相同判斷有沒有在同一群
方法 |
建立 |
連結 |
判斷 |
quick-find |
\(N\) |
\(N\) |
\(1\) |
quick-union |
\(N\) |
\(N\) |
\(N\) |
改進 - 避免樹長太深
- 紀錄樹的深度 (weighted quick-union(QU))
- 連結時把矮的樹並到高的樹中

原因
- 要讓 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)
- \(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\) |
Union-Find source: Coursera Algorithms, Part 1 Algorithms, 4th ed. - [Sedgewick, Wayne]
{"metaMigratedAt":"2023-06-14T12:53:37.301Z","metaMigratedFrom":"Content","title":"Union-Find","breaks":true,"contributors":"[]"}