Disjoint Set 是將一個集合(set)拆成若干個互斥集合，也就是說所有子集合彼此交集為 ∅，且聯集為原集合的資料結構。
- Basic Concept about Disjoint Set
- Disjoint Set's Naive Operation to detect graph cycle
- Disjoint Set’s Improved Operation to detect graph cycle
Remark Table :
╔═══════════╦════════════════════╦═══════════════╗
║ Opeartion ║ Time cost ║ comment ║
╠═══════════╬════════════════════╬═══════════════╣
║ Union ║ O(1) ║ ║
╠═══════════╬════════════════════╬═══════════════╣
║ Find ║ O(height) ║ ║
╠═══════════╬════════════════════╬═══════════════╣
║ Union ║ O(1) ║ ║
║ by Height ║ ║ ║
╠═══════════╬════════════════════╬═══════════════╣
║ Find with ║ O(logN) ║ ║
║Compression║ ║ ║
╚═══════════╩════════════════════╩═══════════════╝考慮一群互斥集合 :
S1={1,2,3} S2={7,8,10} S3={4,5,6,9}a.)可以將每個set使用 " Tree " 來表示 : (set中任取一點作為root)
b.)可以用 " Array "來表示 :
If parent[i]≥0，表示point to parent，else (parent[i]<0),point to NIL
+---------+----+----+----+----+----+----+----+----+----+----+
| Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| ------- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- |
| Data | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Paraent | -1 | 1 | 1 | 5 | -1 | 5 | -1 | 7 | 5 | 7 |
+---------+----+----+----+----+----+----+----+----+----+----+上表可以看出2,3的Pointer都指向1，而1的Pointer指向Nil， 同樣4,6,9指向5，而8,10指向7。
以上兩種方法都是能夠建立Disjoint Set的基本方法以及概念，等等能利用Disjoint Set的基本運算來實現判斷圖的Cycle的方法。
Disjoint Set’s Naive Operation
Union : Join two subsets into a single subset.
Find : Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.’
Union operation
Union(s1,s2):任取s1或s2的root作為new root，另一set成為他的子樹。
Find operation
沿著某一 element不停地透過其parent往上找尋能夠代表此subset的root。
Detect Graph Cycle
我們可以用Array 表示法來判斷一個Graph是否含有” Cycle “ :
對於每個edge(u,v)，若 u,v屬於不同subset，我們執行Union operation 將 u,v放進同一個subset ; 反之，如果 u,v在同一個subset，則表示找到一組cycle 。
一開始, Array的parent欄位皆初始化為-1(表示每個節點都自成一個集合)
+---------+----+----+----+
| Index | 1 | 2 | 3 |
| ------- | -- | -- | -- |
| Data | 0 | 1 | 2 |
| Paraent | -1 | -1 | -1 |
----------+----+----+----+現在開始對每個edge進行判斷 :
1.) Edge (0,1): 查詢頂點0和1屬於哪個子集合，因為他們在不同的子集合 ， 所以我們對這兩點做Union operation 。這邊選擇將1成為0的Parent。
(可以選擇將1成為0的Parent，也可以將0成為1的Parent )
+---------+----+----+----+
| Index | 1 | 2 | 3 |
| ------- | -- | -- | -- |
| Data | 0 | 1 | 2 |
| Paraent | 1 | -1 | -1 | (表示"1"已經成為"0"的Parent)
----------+----+----+----+2.)Edge (1,2): 因為1屬於subset 1 而 2 屬於 subset 2 . 因此我們做Union
+---------+----+----+----+
| Index | 1 | 2 | 3 |
| ------- | -- | -- | -- |
| Data | 0 | 1 | 2 |
| Paraent | 1 | 2 | -1 | (這邊"2"已經可以表示{0,1,2}這個 subset-2了)
----------+----+----+----+3.)Edge (0,2): 因為0 已經屬於 subset 2 而且 2 也屬於 subset 2.
因此，如果加入這個edge便會形成Cycle。
Disjoint Set’s Improved Operation
上述的Union方法有可能製造出一棵Skew Tree，而使Find operation的複雜度達到天高的情況，因此我們必須要改善Union的方法而使Find更有效率。
Union-by-rank
這邊使用 ” rank ”這個term，而不是"height"，因為如果Find operation使用了"Path Compression"這項技術的話，便不只是使用union-by-height，而是使用Tree’s size來做選擇哪一個Tree的root來作為整體的root。
Union-by-height
使用height作為"weighting rule"。
高度相同，高度+1。
否則，高度不變。Union-by-height能夠產生高度頂多為O(logN)的Tree.
使得Find Operation 平均cost : O(logN)
Path Compression
also called as “collapsing rule”
Key Idea : 每次Find(x)時，除了找出x所在Set之root之外，另外會其Path上的所有Node(包含 x)的所有Pointer 一同指向Root。
Some implementation Code Tips:
如果使用以下定義來implent subset的話 ..
每一個Node的節點都有一個pointer指向其Parent。
除了Root之外，”其 Pointer為指向自己 ”。
Make_Set(x):
x.parent := x //point to itself
x.rank := 0
x.size := 1Find(x): //Find with compression
if x.parent != x
x.parent := Find(x.parent)//遞迴去找Parent，x.parent=x時終止。
return x.parentUnion(x, y): //Union by rank
xRoot := Find(x)
yRoot := Find(y)
if xRoot == yRoot // x和y在同一个集合。
return
// x和y不在同一个集合，Union by rank。
if xRoot.rank < yRoot.rank
xRoot.parent := yRoot
else if xRoot.rank > yRoot.rank
yRoot.parent := xRoot
else //x.subset's rank =y.subset's rank
yRoot.parent := xRoot
xRoot.rank := xRoot.rank + 1 //高度相同rank才+1
Reference
