Home Algorithm

Union-Find data structure 又稱 Disjoint-set data structure，用於處理不相交集合 (disjoint set) 的合併 (Union) 與查詢 (Find) 問題。

# Disjoint Set

Disjoint set 表示數個 set 之間，擁有的元素都不相同，彼此互斥 (disjoint)。

可以去看看這篇文章 - disjoint set

# Union Find Algorithm

Union-Find Data Structure 是一種 forest 結構，forest 是一種 N-way Tree 結構，互相連通的節點放在同一個 set，任意選擇其中一個節點作為 root。

Union Find 提供以下兩種操作:

  • Find: 找到 input 節點的 root，可以藉此確定 input 節點屬於哪個子集。

    • Find 函數能夠找到節點的 root。
    • 如果要確認兩個節點是否為同一子集，只要分別找兩個節點的 root ，如果一樣，即屬於同一子集 (為 connected component)。
    • Find 的時間複雜度最差就是遍歷整棵樹，時間複雜度為 O (n)。

  • Union: 將兩個子集合併為同一子集。

    • Union 能夠將兩個所屬的子集進行合併。
    • 最簡單的方法就是將一個子集的 root 直接作為另一子集 root 的子節點即可

    • Union 的實踐需要依靠 find，因此時間複雜度最差為 O (n)。

以上圖的兩個樹來說，以 0 為 root 的樹大於以 2 為 root 的樹，如果將後者合併到前者下，合併過後的樹高度會比較小，根據這個觀察可以歸納出，如果兩個子集要合併，應該讓高度較小的子集合併到高度比較大的子集下，可以避免樹的不平衡。

# Find with Path Compression

Path compression 是一個優化技巧，也有人稱為 set collapsing, 讓每個節點直接連到它的 root 節點，這樣 Find 跟 Union 操作的時間複雜度可以降到 O (1)。

但要如何有效地讓所有節點 parent node 都指向 root 呢？
答案就是透過遞迴，透過遞迴找到 root， 再依序回傳更新為每個走訪過的 parent。

int find(int x) {
    if (x == root[x]) return x;
    return root[x] = find(root[x]);
}

# Union by Size/Rank

應用 path compression 後的樹可以盡可能縮減樹的高度 ，若要再 Union 兩個壓縮後的子集，可以採取 union by size 技巧，將子節點比較少的 root 加入比較大的子集。

依照 rank 來排序，起初每個點的 rank 均為 0 ，依據 rank 大小來決定如何合併，rank 大的子集合併小的，合併別人的子集其 rank 往上增加。

void unionSet(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);
    if (root_x == root_y) return ;
    if (rank[root_x] > rank[root_y]) root[root_y] = root_x;
    else if (rank[root_x] < rank[root_y]) root[root_x] = root_y;
    else {
        root[root_y] = root_x;
        rank[root_x]++;
    }  
}

一開始每個點的 rank 都為 0 ，有一點特別容易寫出 bug ，在比較彼此 rank 或是更新 rank 時候，需要以 find() 所找出的 root 來比，不是各個節點本身的 rank 。