圖論演算法ch21 — DS for Disjoint Sets

什麼是disjoint set？

1. 用來維護一個(大)集合的(小)集合，也稱作union find
2. 每個集合都有一個代表者，代表者是集合中的元素
3. 集合不變，代表者也不能變
4. 常用來檢測圖是否相連

disjoint set 的 operation

1. Make-Set(x)：產生只包含x的集合，並放到S中
2. Union(x, y)：將包含x的集合和包含y的集合合併
3. Find-Set(x)：找到x的代表者

用linked list來表示disjoint set

1. list的第一個元素，就是集合的代表者
2. 每個元素都有指標指到代表者
3. 有head&tail兩個指標

用linked list表示disjoint set

1. Make-Set(x)：O(1)
2. Union(x, y)：O(y-list的個數)
3. Find-Set(x)：O(1)

linked-list union(g, e)

⚠️問題：Union太花時間⚠️

Linked-List Union改善方法

每次都更新數量較少的集合

令 m = operation的次數(Make-Set, Union, Find-Set)
令 n = Make-Set的次數
全部花O(m+nlgn)

proof.
每次都更新數量較少的集合
一個元素最多更新lgn次
總共有n個元素->Union需花O(nlgn)
Make-Set&Find-Set最多花O(m)
->所有加起來最多花O(m+nlgn)

用forest set來表示disjoint set

1. 用tree來表示集合
2. 每個元素指向自己的parent
3. root就是集合的代表
4. root是自己的parent

用tree來表示disjoint set

1. Make-Set(x)：O(1)
2. Union(x, y)：O(h)，h是樹高
   //先找到代表者，再合併
3. Find-Set(x)：O(h)，h是樹高

forest set Union(h, g)

⚠️問題：有可能產生chain⚠️

產生chain

forest set 改善方法

1. Union by rank：將rank小的樹 變成 rank大的樹 的兒子
   //rank是樹高的上界(不一定等於樹高)
   只用Union by rank -> O(mlgn)
2. Path compression：將路上遇到的點都變成root的兒子
   只用Path compression -> Θ(n+ f⋅(1 +log(2+ f/n)n))
   //2+f/n 是log下面小的那個

path compression

同時使用，最差情況O(m*a(n))
合理情況下，a(n)≤4
//不用會證沒關係

程式碼