Union-Find data structure ，又稱為 disjoint-set data structure，用於處理 disjoint set 的查詢與合併問題，最常見應用，用來解決圖中的 connected component 問題 。
Disjoint set
先看 "set" 這個單字，set 在 computer science 領域指的是一組資料的集合，set 內部的資料是不重複的，資料之間的順序並不重要。
而 disjoint set 表示數個 set 之間，擁有的元素都不相同，彼此互斥（disjoint）。例如 A = {1, 2, 3}, B = {4, 5} ，A 和 B 即為 disjoint set 。
Union-Find Algorithm
Union-Find data structure 是一種 forest 結構，forest 是一種 N-way Tree 結構，互相連通的節點放在同一組 set ，並以 forest 來表示，任意選擇其中一個節點作為 root 。
Union-Find 提供以下兩種操作：
- Find : 確定元素屬於哪一個子集 (找到節點的 root )。可以使用此操作確定兩個元素是否屬於同一子集。
- Union : 將兩個子集合併為同一子集。
Find 函數背後概念為找到節點的 root ，如果要確認兩個節點是否屬於同一子集，只要分別找兩節點的 root ，如果一樣，即代表屬於同一子集。
Find 的時間複雜度，最差狀況就是遍歷整棵樹，若樹呈現極度不平衡如同一個 linked list ，時間複雜度為 O (n) 。
Union 能夠將兩個點所屬的子集進行合併，合併最簡單方法是將一個子集的 root 直接作為另外一個子集 root 的子節點即可，如下圖：
Union 的實現需要依靠 Find ，因此時間複雜度最差將為 O (n) 。
Find 跟 Union 的執行時間都是線性等級，這樣的資料結構顯然不是好用的，你可能會想到平衡二元樹，其樹的高度維持在 O (log n) ，因此想要改善時間複雜度，最好是避免樹的不平衡。
Weighted Quick Union - Tree 平衡優化
以上圖來說，如果由 2 作為 0 的子節點，合併過後的樹高度會比較小，根據這個觀察可以歸納出，如果兩個子集要合併，應該讓高度較小的子集合併到比較大的子集下。
Path Compression
Path compression 可以進一步優化，讓每個節點直接連到他的 root 節點，這樣 Find 跟 Union 操作的時間複雜度可以降低到 O (1) 。
要達成壓縮，只需在 Find 中加入以下程式碼，建議可以自己畫圖感受程式碼的行為，while 終止條件為節點的 parent 等於自己，代表無法再壓縮了，壓縮完的 tree 的高度一定不大於 3 。
int Find(int a) {
while (a != parents[a]) {
// a's grandparent is now a's parent
parents[a] = parents[parents[a]];
a = parents[a];
}
return a;
}
Union by size / rank with path compression
透過 path compression 後的樹可以維持高度在 3 以內 ，若要再 union 兩個壓縮後的子集，可以採取 union by size 技巧，將子節點比較少的 root 加入比較大的子集。
另外一種是依照 rank 來排序，起初每個點的 rank 均為 0 ，依據 rank 大小來決定如何合併，rank 大的子集合併小的，同時前者的 rank 往上增加。
如果有了 path compression ，是否還需要依據 size 或 rank 來決定合併順序？
有了 path compression ， forest 的高度必定不超過 3 ，維持在常數等級，由時間複雜度角度來看確實沒有差別，但由下圖合併完的兩個 case 來看，情況 1 會另外做好幾次的 path compression 來將第三層的節點移到第二層，因此依據 size 或 rank 來決定合併確實更佳優化。
Leetcode #200 Number of Islands
題目所求就是從圖中找出 component 數量。
class UnionFind 負責處理 union-find data structure ，在 class UnionFind 的 Constructor 中，針對每個 land 節點先將其 parent 設為自己，也代表每個節點自己都是一個 connected component ，而 water 節點的 parent 設為 -1 。
透過 DFS 由每個 land 出發，走訪過的點直接修改為 water 節點，避免被重複執行 Union ，每執行一次 Union ，代表少了一個 component 數量，所有 land 都透過 DFS 走訪過，即可得 component 數量。
class UnionFind {
public:
UnionFind(vector<vector<char>>& grid) {
count = 0;
for (int i=0; i<grid.size (); i++)
{
for (int j=0; j<grid[0].size (); j++)
{
if (grid[i][j] == '1')
{
parent.push_back (i*grid[0].size() + j);
count++;
}
else
{
parent.push_back (-1);
}
rank.push_back (i*grid[0].size() + j);
}
}
}
int find(int i) { // path compression
while (i != parent[i])
{
parent[i] = parent[parent[i]];
i = parent[i];
}
return parent[i];
}
void Union(int x, int y) { // union with rank
int root_x = find (x);
int root_y = find (y);
if (root_x != root_y)
{
if (rank[root_x] > rank[root_y])
{
parent[root_y] = root_x;
}
else if (rank[root_y] > rank[root_x])
{
parent[root_x] = root_y;
}
else
{
parent[root_y] = root_x;
rank[root_x] +=1;
}
count--;
}
}
int getCount() const {
return count;
}
private:
vector<int> parent;
vector<int> rank;
int count; // # of connected components
};
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int col = grid.size ();
int row = grid[0].size ();
UnionFind uf (grid);
for (int i=0; i<col; i++)
{
for (int j=0; j<row; j++)
{
if (grid[i][j] == '1')
{
grid[i][j] = '0';
if (i-1 >= 0 && grid[i-1][j] == '1') uf.Union (i*row+j, (i-1)*row+j);
if (i+1 < col && grid[i+1][j] == '1') uf.Union (i*row+j, (i+1)*row+j);
if (j-1 >=0 && grid[i][j-1] == '1') uf.Union (i*row+j, i*row+(j-1));
if (j+1 < row && grid[i][j+1] == '1') uf.Union (i*row+j, i*row+(j+1));
}
}
}
return uf.getCount ();
}
};時間複雜度
時間複雜度為 O (M x N) ，M, N 分別為輸入陣列的長跟寬，最壞狀況下 DFS 會將所有點都走過。
空間複雜度
空間複雜度為 O (M x N) ，每個點需要紀錄其 parent 與 rank 。
Leetcode #684 Redundant Connection
本題要問去除哪一個 edge 來避免圖中形成 cycle ，回想 Union-Find algorithm ，Union 方法就是將兩個子集合在一起，並形成一個新的 forest 結構，但是兩個子集可以合為一個 forest ，是根基於兩個子集沒有交集，也就是說他們的 root 不一樣，若是兩子集有共同 root ，又將兩個點連起來，就會在 forest 中形成 cycle 。
將每個 edge 的兩點 union 起來，在 Union 操作內將執行 Find 找兩點的 root， 若 root 一樣，代表找到會形成 cycle 的 edge 。
class Solution {
public:
vector<int> parent;
vector<int> rank;
int Find (int x)
{
while (x != parent[x])
{
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
bool Union (int x, int y)
{
int rootX = Find (x);
int rootY = Find (y);
if (rootX == rootY)
{
return false;
}
else
{
if (rank[x] > rank[y])
{
parent[y] = x;
}
else if (rank[y] > rank[x])
{
parent[x] = y;
}
else
{
parent[rootX] = rootY;
rank[y]++;
}
}
return true;
}
vector<int> findRedundantConnection(vector<vector<int>>& edges)
{
for (int i=0; i<= edges.size(); i++)
{
parent.push_back (i);
rank.push_back (0);
}
for (int i=0; i<edges.size(); i++)
{
if (!Union (edges[i][0], edges[i][1]))
{
return vector<int> {edges[i][0], edges[i][1]};
}
}
return {};
}
};時間複雜度
O (N) ，其中 N 可能為題目給的 edge 數量或是 node 數量。
空間複雜度
O (N) ，N 為 node 數量。
延伸問題 Leetcode #261, #547, #721
Reference
- Disjoint Set Union CP-Algorithms
- Disjoint-set data structure - wikipedia
- 普林斯頓課程學習筆記1-union-find
- 演算法筆記 Set
- http://web.ntnu.edu.tw/~algo/SpanningTree.html#2
- Union-Find算法详解 - labuladong算法博客
Updated on 2021-02-24 20:16:38 星期三