关于 并查集(union find) 算法基本原理 以及 其 在分布式图场景的应用
二月的最后一篇水文…想寫一些有意思的東西。
文章目錄
- 環(huán)檢測在圖數(shù)據(jù)結構中的應用
- 深度/廣度優(yōu)先 檢測環(huán)
- 并查集數(shù)據(jù)結構 (Union-Find)
- 基本概念
- 初始化
- 合并 union
- 查找祖先
- 優(yōu)化1: 合并過程 利用 rank 優(yōu)化路徑
- 優(yōu)化2: 路徑壓縮(Path Compression)
- 并查集 解決圖中檢測環(huán)問題
環(huán)檢測在圖數(shù)據(jù)結構中的應用
我們在圖數(shù)據(jù)結構場景中會有一些判斷是否存在環(huán)的需求，大多數(shù)的判斷場景是在有向圖中：
- 比如我們在圖數(shù)據(jù)存儲場景中想要拓撲好友關系，比如查找某一個人到另一個人的好友關系鏈，這個檢索過程需要是一個有向無環(huán)圖的檢索過程，是不能出現(xiàn)環(huán)的，需要在檢索過程中能夠檢測到環(huán)的存在。
- 再比如 我們在分布式事務場景中，比如悲觀事務的實現(xiàn)中往往需要有一個 單key 事務鎖 在并發(fā)場景的 wait 鎖關系的構造 Rocksb 事務鎖實現(xiàn) – 死鎖檢測部分，這個時候需要對多個事務的 wait鎖 之間的互相等待關系構造一個 wait-circle，并且需要在一個元素插入之后檢測改有向圖是否存在環(huán)，存在則需要回退這次的插入。
當然，實際應用到圖存儲/計算的場景還有很多，對環(huán)的檢測需求也都是一直存在的。
深度/廣度優(yōu)先 檢測環(huán)
在這種場景下我們一般檢測環(huán)存在的做法是遍歷圖，主要使用兩種方式 (bfs/dfs) :
這兩種實現(xiàn)方式都比較簡單，利用一個visited 數(shù)組保證訪問過程中除非遇到環(huán)，否則不會訪問到自己。
下面這個有向圖在遍歷的過程中會出現(xiàn)環(huán)，在分布式事務的場景下 wait-circle 就是出現(xiàn)死鎖了，這種情況下是必須要檢測出環(huán)的。
如下使用深度優(yōu)先搜索來進行環(huán)的查找，前置條件就是使用鄰接矩陣來標識圖中的頂點，比如坐標[i,j] = 1，標識i --> j 即頂點 i 和頂點 j 連通；為 0 則表示兩個頂點不連通。
查找的算法也很簡單：
- 增加輔助訪問數(shù)組 visited，標識頂點 i 被訪問過。
- 遍歷鄰接矩陣 且 visited 為 false 的頂點
- 深度優(yōu)先搜索 所有以 i 為頂點的 [i,j] = 1 即 i --> j ，i --> k的頂點，如果發(fā)現(xiàn)某一個頂點 visited[j]=true，那么就標識已經(jīng)找到環(huán)了，否則繼續(xù)深度優(yōu)先查找。
// 通過鄰接矩陣 matrix 保存有向圖
vector<vector<int>> matrix;
bool isCircle(）{// 初始化visit 數(shù)組，標識已經(jīng)訪問過的節(jié)點int m_size = matrix.size();vector<bool> visited(m_size, false);for (int i = 0;i < m_size; i++) {if (!visited[i]) {// 傳入當前訪問的下標，訪問標識數(shù)組，最后就是父節(jié)點(上一個訪問的節(jié)點)// 找到了環(huán)，就返回真即可.if (dfs_search(i, visited)) {return true;}}}// 整個矩陣都遍歷完成還是沒有找到，就認為是無環(huán)return false;
}// dfs 查找環(huán)
bool dfs_search(int current_idx, vector<bool>& visited) {visited[current_index] = true;// 查找 current_idx 即當前節(jié)點的連通節(jié)點for (int i = 0;i < matrix[current_idx].size(); i++) {// 如果為1，則標識當前current_idx 指向 i，那么check一下這個指向的節(jié)點是否訪問過，// 那就是找到環(huán)了。if (matrix[current_idx][i] == 1) {if ( visited[i] && i != current_idx) return true;else {if (dfs_search(i, visited)) return true;}}}return false;
}
廣度優(yōu)先算法也很類似（層次遍歷），同樣是通過visited 輔助數(shù)組來實。
和dfs的差異只是利用隊列來提前將 current_idx 的所有指向的兄弟節(jié)點先添加到隊列中，再進行下一層的查找，如下代碼。
// 通過鄰接矩陣 matrix 保存有向圖
vector<vector<int>> matrix;
bool isCircle(）{int m_size = matrix.size();vector<bool> visited(m_size, false);// 保存當前訪問的頂點for (int i = 0;i < m_size; i ++) {if (!visited[i]) {if (bfs_search(i, visited)) return true;}}return false;
}bool bfs_search(int curr_idx, vector<bool>& visited) {queue<int> qu;qu.push(curr_idx);visited[curr_idx] = true;while (!qu.empty()) {int size = qu.size();// 按層遍歷for (int j = 0;j < size; j++) {int curr_idx = qu.front();qu.pop();// 需要將 curr_idx 所有的臨接頂點 先check 環(huán)是否存在，不存在則添加到queue中for (int k = 0;k < matrix[curr_idx].size(); k++) {if (matrix[curr_idx][k] == 1) {if (curr_idx != k && visited[k]) return true;else {qu.push(k);// 標記 curr_idx --> k 的 k頂點已經(jīng)被訪問過了visited[k] = true;}}}}}return false;
}
以上兩種實現(xiàn)方式都是非常基礎的圖中的環(huán)的檢測，都是是能夠正確得檢測出環(huán)的存在。
但是性能問題卻很明顯，每一次的檢測都需要對整個圖進行一個大的scan，對于一個 m*n 的超大矩陣 (我們普通的分布式圖存儲集群中往往擁有超過百萬/千萬級別的頂點和 總數(shù)目近萬億的邊)，在這樣的圖網(wǎng)絡中去檢測環(huán)，利用上面的方式效率可以說是極低的。當然，現(xiàn)在最通用的解決辦法就是限制查找的層數(shù)。
索引好友關系列表的話也僅僅只會索引3度的出邊列表，在分布式事務中的wait-circle 中也會限制死鎖檢測的深度；但是當我們想要查找兩個無關頂點之間的最短到達路徑的時候，這個過程中的環(huán)檢測避免不了，那有沒有更加高效的算法，在不用每次插入一個元素都進行一次全鏈路遍歷檢測環(huán)呢？
當然有～～～, 聰明的人無處不在，并查集 應運而生。
并查集數(shù)據(jù)結構 (Union-Find)
基本概念
并查集是一種數(shù)據(jù)結構，其支持對不相交的集合（disjoint sets）執(zhí)行如下一些操作：
- makeSet(e) 這是 并查集數(shù)據(jù)結構中的一個操作，用來將輸入的元素 e 插入到一個集合中，并返回包含這個元素e 的集合的根節(jié)點。
- Union(A,B) 合并兩個集合 A,B
- Find(e) 返回包含元素e 的集合
基本概念其實是很晦澀的，直接來看并查集的這幾個操作就好。
并查集中的集合元素組織有兩種形態(tài)：鏈表形態(tài) 和 樹形態(tài)。
原本我們的鏈表/樹 形態(tài)，會記錄 parent–>child 或者 prev --> next 這樣的關系，而并查集中對數(shù)據(jù)集的標識 是記錄 next 的 prev節(jié)點 或者說 是記錄 child 的 parent 節(jié)點信息。
其中樹形態(tài)的并查集 表示 方式其實是鏈表形態(tài)的一種優(yōu)化（路徑壓縮），能夠極大得降低元素查找的層數(shù)；當然， 在圖的環(huán)優(yōu)化中，這兩種形態(tài)可以分別用于有向圖（鏈表形態(tài)，保存了集合中的方向關系）和 無向圖（不需要方向關系）的表示。
接下來，我們看看并查集的每個操作實現(xiàn)。
初始化
對集合中的每一個元素，他們的父節(jié)點應該為 空 或者 也可以指向自己（指向自己的這種初始化方式就不能應用在圖的環(huán)判斷中了，可以用于正常的集合操作）。
本文演示均用-1 表示空
雖然前面說并查集的數(shù)據(jù)結構 有兩種形態(tài)， 鏈表或者樹，但是實際我們應用的時候，可以采用數(shù)組/無序map 的方式就夠了。
unorder_map<int,int> father;
void Add(int ele) {if (!father.count(ele)) {father[ele] = -1; }
}
合并 union
這個操作主要是check 兩個節(jié)點是否可以連通（祖先是不同的）， 如果是連通的，那就要進行合并，讓他們擁有相同的祖先。
這里兩個節(jié)點 誰當祖先都是可以的。
void union(int x, int y) {int x_root = find(x);int y_root = find(y);// 祖先不同，則發(fā)現(xiàn)是兩個不同的集合，則可以對他們進行合并if (x_root != y_root) {fater[x_root] = y_root;}
}
查找祖先
如果節(jié)點的父節(jié)點不為空，那就需要持續(xù)查找，直到找到父節(jié)點為空的節(jié)點，就是當前輸入的ele 的祖先節(jié)點。
我們想要查找節(jié)點 12 的祖先節(jié)點，就需要不斷的check father節(jié)點，直到father節(jié)點為空(或者是自己)。
int find(int ele) {int root = ele;while (father[root] != -1) {root = father[root];}return root;
}
這里是有可以優(yōu)化的地方，我們希望在并查集中的節(jié)點分布能夠更接近樹形態(tài)，而不是鏈表形態(tài)。畢竟樹形查找的復雜度是小于等于(O(log_n))，也就是我們可以將鏈表形態(tài)的并查集結構轉(zhuǎn)換為樹形態(tài)。
這樣做可行的原因是 對于并查集中的節(jié)點來說連通性是可以傳遞的， 節(jié)點之間互相連通的標記只需要擁有一個相同的祖先就好了。
大體過程如下：
就是將上圖中左側(cè)一段鏈式結構可以合并成右側(cè)的樹形結構。
優(yōu)化1: 合并過程 利用 rank 優(yōu)化路徑
rank 是一個在前面father基礎上額外增加的一個數(shù)據(jù)結構，標識當前節(jié)點距離祖先節(jié)點的長度，這樣我們的初始化以及合并代碼就變成下面的樣子：
typedef struct UnionFindNode {UnionFindNode* father;int rank;UnionFindNode() : father(nullptr),rank(0) {}bool operator==(const UnionFindNode& lhs) {return father == lhs.father && rank == lhs.rank;}
}Node;void MakeSet(Node& ele) {ele.father = nullptr;ele.rank = 0;
}void Union(const Node x, Node y) {// 找到他們的公共祖先節(jié)點auto xRoot = Find(x);auto yRoot = Find(y);if (xRoot == yRoot) {return;}// 他們不在同一個集合，則需要合并他們的祖先。// 將距離比較短的合并到距離長的祖先上。if (xRoot->rank < yRoot->rank) {xRoot->father = yRoot;} else if (xRoot->rank > yRoot->rank) {yRoot->father = xRoot;} else { //rank 相等，互相指向誰都無所謂，需要增加指向后的被指向節(jié)點的rank（增加了一個元素的深度）。xRoot->father = yRoot;yRoot->rank += 1;}
}
優(yōu)化2: 路徑壓縮(Path Compression)
當然，以上優(yōu)化方式也能夠利用rank 達到我們將鏈表轉(zhuǎn)換成樹的目的，但是需要一個額外的rank 字段，每一個節(jié)點都會多消耗4bytes 的內(nèi)存 。
其實還有一種更簡潔優(yōu)雅的優(yōu)化方式，就是 路徑壓縮。
rank 的優(yōu)化是在 Union 操作的時候，這里路徑壓縮 則是在 Find的時候。
// 還是繼續(xù)使用基本的 unorder_map 保留信息
unordered_map<int, int> father;// 查找節(jié)點 i 的祖先節(jié)點
int Find(int i) {int root = i;// -1 是我們在最前面 Add 一個新的并查集節(jié)點的時候// 會將這個節(jié)點的父節(jié)點設置為 -1，標識它目前是一個單獨的集合。while(father[root] != -1) {root = father[root];}// 路徑壓縮的過程while (i != root) {int origin_father = father[i];father[i] = root;// 關鍵！進行路徑壓縮，將節(jié)點i 的父節(jié)點直接指向祖先節(jié)點。i = origin_father;}return root;
}
比如對于這樣的一個并查集集合，我們想要查找 6。
經(jīng)過路徑壓縮之后， 6 包括整個之前的節(jié)點都會嘗試進行一次路徑壓縮。
關于路徑壓縮的時間復雜度證明較為復雜，這個推演是通過 阿克曼函數(shù) 進行推演的。
總之表示方式是 O(log*n)，其中 log*n表示 n 取多少次 log2nlog_2nlog2?n并向下取整之后變成1，可以理解為是 O(1) 級別。
比如 log*2^65526 ，2^65536 在阿克曼函數(shù)中表示的是 A(4,3) 的結果，基本是人類思維極限的數(shù)字，而 在 log*n 下僅僅只有 5。
關于路徑壓縮時間復雜度的推演 以及 證明 可以參考 The math in Union-Find.
并查集 解決圖中檢測環(huán)問題
回到我們最初 圖中檢測環(huán)的問題，我們接下來可以利用并查集的幾個操作輕松解決。
對于 0 --> 1 --> 2，構造出來的并查集結構 經(jīng)過路徑壓縮 是 0 --> 2 <-- 1 ；而如果存在環(huán)，也就意味著 2 --> 0，對于并查集來說 我們只需要 提前 find (0) 和 find(2) 是否相等，如果相等，則認為當前的插入是會造成環(huán)的（0 已經(jīng)存在 且 其祖先節(jié)點是2）。
實現(xiàn)如下：
class UnionFind {
public:// void Add// void Union// int Find// bool IsConnected
private:unordered_map<int,int> father_;
}
// 通過鄰接矩陣 matrix 保存有向圖
vector<vector<int>> matrix;
bool IsCircle() {UnionFind uf;for (int i = 0;i < matirx.size(); i++) {// 添加每一個節(jié)點到并查集之中uf.Add(i);for (int j = 0;j < i; j++) {if (matrix[i][j]) {int x_root = Find(i);int y_root = Find(j);// 發(fā)現(xiàn)了兩個不同節(jié)點的祖先節(jié)點相等，則找到了環(huán)if (x_root == y_root && i != j) return true;// 否則，是兩個可以連通的節(jié)點，那就需要合并這兩個集合（他們的祖先直接合并就好了）。if (x_root != y_root) uf.Union(x_root,y_root);}}}return false;
}
通過并查集，我們能夠在有節(jié)點更新的情況下非常高效得O(1) 的時間內(nèi)確認這個節(jié)點插入后圖中是否存在環(huán)。
除了檢測環(huán)之外，并查集在圖數(shù)據(jù)結構的其他方向也有非常高效的應用，比如確認圖中兩個頂點是否連通，高效合并兩組無關聯(lián)的圖等等。
總的來說，并查集這個數(shù)據(jù)結構 利用阿克曼函數(shù) 在集合論 以及 圖數(shù)據(jù)結構領域中 能夠非常高效得判斷集合交集 以及 圖節(jié)點連通情況，思想值得學習研究。
總結
以上是生活随笔為你收集整理的关于 并查集(union find) 算法基本原理 以及 其 在分布式图场景的应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 拙字开头的成语有哪些？
- 下一篇： SNMP introduction