電子發(fā)燒友App
記得我之前在講?圖論算法基礎(chǔ)?時(shí)說(shuō)圖論相關(guān)的算法不會(huì)經(jīng)常考，但最近被打臉了，因?yàn)橐恍┳x者和我反饋近期求職面試涉及很多圖論相關(guān)的算法，可能是因?yàn)榄h(huán)境不好所以算法這塊更卷了吧。
常見(jiàn)的圖論算法我都已經(jīng)寫(xiě)過(guò)了，這里按難度順序列舉一下：
圖論算法基礎(chǔ)
二分圖判定算法及應(yīng)用
環(huán)檢測(cè)/拓?fù)渑判蛩惴皯?yīng)用
并查集算法及應(yīng)用（本文）
Kruskal 最小生成樹(shù)算法及應(yīng)用
Prim 最小生成樹(shù)算法及應(yīng)用
Dijkstra 算法模板及應(yīng)用
并查集（Union-Find）算法是一個(gè)專門(mén)針對(duì)「動(dòng)態(tài)連通性」的算法，我之前寫(xiě)過(guò)兩次，因?yàn)檫@個(gè)算法的考察頻率高，而且它也是最小生成樹(shù)算法的前置知識(shí)，所以我整合了本文，爭(zhēng)取一篇文章把這個(gè)算法講明白。
首先，從什么是圖的動(dòng)態(tài)連通性開(kāi)始講。
一、動(dòng)態(tài)連通性
簡(jiǎn)單說(shuō)，動(dòng)態(tài)連通性其實(shí)可以抽象成給一幅圖連線。比如下面這幅圖，總共有 10 個(gè)節(jié)點(diǎn)，他們互不相連，分別用 0~9 標(biāo)記：
現(xiàn)在我們的 Union-Find 算法主要需要實(shí)現(xiàn)這兩個(gè) API：
class?UF?{
????/*?將?p?和?q?連接?*/
????public?void?union(int?p,?int?q);
????/*?判斷?p?和?q?是否連通?*/
????public?boolean?connected(int?p,?int?q);
????/*?返回圖中有多少個(gè)連通分量?*/
????public?int?count();
}
?
?
這里所說(shuō)的「連通」是一種等價(jià)關(guān)系，也就是說(shuō)具有如下三個(gè)性質(zhì)：
1、自反性：節(jié)點(diǎn)p和p是連通的。
2、對(duì)稱性：如果節(jié)點(diǎn)p和q連通，那么q和p也連通。
3、傳遞性：如果節(jié)點(diǎn)p和q連通，q和r連通，那么p和r也連通。
比如說(shuō)之前那幅圖，0～9 任意兩個(gè)不同的點(diǎn)都不連通，調(diào)用connected都會(huì)返回 false，連通分量為 10 個(gè)。
如果現(xiàn)在調(diào)用union(0, 1)，那么 0 和 1 被連通，連通分量降為 9 個(gè)。
再調(diào)用union(1, 2)，這時(shí) 0,1,2 都被連通，調(diào)用connected(0, 2)也會(huì)返回 true，連通分量變?yōu)?8 個(gè)。
判斷這種「等價(jià)關(guān)系」非常實(shí)用，比如說(shuō)編譯器判斷同一個(gè)變量的不同引用，比如社交網(wǎng)絡(luò)中的朋友圈計(jì)算等等。
這樣，你應(yīng)該大概明白什么是動(dòng)態(tài)連通性了，Union-Find 算法的關(guān)鍵就在于union和connected函數(shù)的效率。那么用什么模型來(lái)表示這幅圖的連通狀態(tài)呢？用什么數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)代碼呢？
二、基本思路
注意我剛才把「模型」和具體的「數(shù)據(jù)結(jié)構(gòu)」分開(kāi)說(shuō)，這么做是有原因的。因?yàn)槲覀兪褂蒙郑ㄈ舾煽脴?shù)）來(lái)表示圖的動(dòng)態(tài)連通性，用數(shù)組來(lái)具體實(shí)現(xiàn)這個(gè)森林。
怎么用森林來(lái)表示連通性呢？我們?cè)O(shè)定樹(shù)的每個(gè)節(jié)點(diǎn)有一個(gè)指針指向其父節(jié)點(diǎn)，如果是根節(jié)點(diǎn)的話，這個(gè)指針指向自己。比如說(shuō)剛才那幅 10 個(gè)節(jié)點(diǎn)的圖，一開(kāi)始的時(shí)候沒(méi)有相互連通，就是這樣：
?
class?UF?{
????//?記錄連通分量
????private?int?count;
????//?節(jié)點(diǎn)?x?的父節(jié)點(diǎn)是?parent[x]
????private?int[]?parent;
????/*?構(gòu)造函數(shù)，n?為圖的節(jié)點(diǎn)總數(shù)?*/
????public?UF(int?n)?{
????????//?一開(kāi)始互不連通
????????this.count?=?n;
????????//?父節(jié)點(diǎn)指針初始指向自己
????????parent?=?new?int[n];
????????for?(int?i?=?0;?i?
如果某兩個(gè)節(jié)點(diǎn)被連通，則讓其中的（任意）一個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)接到另一個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)上：
?
public?void?union(int?p,?int?q)?{
????int?rootP?=?find(p);
????int?rootQ?=?find(q);
????if?(rootP?==?rootQ)
????????return;
????//?將兩棵樹(shù)合并為一棵
????parent[rootP]?=?rootQ;
????//?parent[rootQ]?=?rootP?也一樣
????count--;?//?兩個(gè)分量合二為一
}
/*?返回某個(gè)節(jié)點(diǎn)?x?的根節(jié)點(diǎn)?*/
private?int?find(int?x)?{
????//?根節(jié)點(diǎn)的?parent[x]?==?x
????while?(parent[x]?!=?x)
????????x?=?parent[x];
????return?x;
}
/*?返回當(dāng)前的連通分量個(gè)數(shù)?*/
public?int?count()?{?
????return?count;
}
?
?
這樣，如果節(jié)點(diǎn)p和q連通的話，它們一定擁有相同的根節(jié)點(diǎn)：
?
public?boolean?connected(int?p,?int?q)?{
????int?rootP?=?find(p);
????int?rootQ?=?find(q);
????return?rootP?==?rootQ;
}
至此，Union-Find 算法就基本完成了。是不是很神奇？竟然可以這樣使用數(shù)組來(lái)模擬出一個(gè)森林，如此巧妙的解決這個(gè)比較復(fù)雜的問(wèn)題！
那么這個(gè)算法的復(fù)雜度是多少呢？我們發(fā)現(xiàn)，主要 APIconnected和union中的復(fù)雜度都是find函數(shù)造成的，所以說(shuō)它們的復(fù)雜度和find一樣。
find主要功能就是從某個(gè)節(jié)點(diǎn)向上遍歷到樹(shù)根，其時(shí)間復(fù)雜度就是樹(shù)的高度。我們可能習(xí)慣性地認(rèn)為樹(shù)的高度就是logN，但這并不一定。logN的高度只存在于平衡二叉樹(shù)，對(duì)于一般的樹(shù)可能出現(xiàn)極端不平衡的情況，使得「樹(shù)」幾乎退化成「鏈表」，樹(shù)的高度最壞情況下可能變成?N。
所以說(shuō)上面這種解法，find,union,connected的時(shí)間復(fù)雜度都是 O(N)。這個(gè)復(fù)雜度很不理想的，你想圖論解決的都是諸如社交網(wǎng)絡(luò)這樣數(shù)據(jù)規(guī)模巨大的問(wèn)題，對(duì)于union和connected的調(diào)用非常頻繁，每次調(diào)用需要線性時(shí)間完全不可忍受。
問(wèn)題的關(guān)鍵在于，如何想辦法避免樹(shù)的不平衡呢？只需要略施小計(jì)即可。
三、平衡性優(yōu)化
我們要知道哪種情況下可能出現(xiàn)不平衡現(xiàn)象，關(guān)鍵在于union過(guò)程：
public?void?union(int?p,?int?q)?{
????int?rootP?=?find(p);
????int?rootQ?=?find(q);
????if?(rootP?==?rootQ)
????????return;
????//?將兩棵樹(shù)合并為一棵
????parent[rootP]?=?rootQ;
????//?parent[rootQ]?=?rootP?也可以
????count--;
?
?
我們一開(kāi)始就是簡(jiǎn)單粗暴的把p所在的樹(shù)接到q所在的樹(shù)的根節(jié)點(diǎn)下面，那么這里就可能出現(xiàn)「頭重腳輕」的不平衡狀況，比如下面這種局面：
長(zhǎng)此以往，樹(shù)可能生長(zhǎng)得很不平衡。我們其實(shí)是希望，小一些的樹(shù)接到大一些的樹(shù)下面，這樣就能避免頭重腳輕，更平衡一些。解決方法是額外使用一個(gè)size數(shù)組，記錄每棵樹(shù)包含的節(jié)點(diǎn)數(shù)，我們不妨稱為「重量」：
class?UF?{
????private?int?count;
????private?int[]?parent;
????//?新增一個(gè)數(shù)組記錄樹(shù)的“重量”
????private?int[]?size;
????public?UF(int?n)?{
????????this.count?=?n;
????????parent?=?new?int[n];
????????//?最初每棵樹(shù)只有一個(gè)節(jié)點(diǎn)
????????//?重量應(yīng)該初始化?1
????????size?=?new?int[n];
????????for?(int?i?=?0;?i?
?
?
比如說(shuō)size[3] = 5表示，以節(jié)點(diǎn)3為根的那棵樹(shù)，總共有5個(gè)節(jié)點(diǎn)。這樣我們可以修改一下union方法：
?
?
public?void?union(int?p,?int?q)?{
????int?rootP?=?find(p);
????int?rootQ?=?find(q);
????if?(rootP?==?rootQ)
????????return;
????//?小樹(shù)接到大樹(shù)下面，較平衡
????if?(size[rootP]?>?size[rootQ])?{
????????parent[rootQ]?=?rootP;
????????size[rootP]?+=?size[rootQ];
????}?else?{
????????parent[rootP]?=?rootQ;
????????size[rootQ]?+=?size[rootP];
????}
????count--;
}
?
?
這樣，通過(guò)比較樹(shù)的重量，就可以保證樹(shù)的生長(zhǎng)相對(duì)平衡，樹(shù)的高度大致在logN這個(gè)數(shù)量級(jí)，極大提升執(zhí)行效率。
此時(shí)，find,union,connected的時(shí)間復(fù)雜度都下降為 O(logN)，即便數(shù)據(jù)規(guī)模上億，所需時(shí)間也非常少。
四、路徑壓縮
這步優(yōu)化雖然代碼很簡(jiǎn)單，但原理非常巧妙。
其實(shí)我們并不在乎每棵樹(shù)的結(jié)構(gòu)長(zhǎng)什么樣，只在乎根節(jié)點(diǎn)。
因?yàn)闊o(wú)論樹(shù)長(zhǎng)啥樣，樹(shù)上的每個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)都是相同的，所以能不能進(jìn)一步壓縮每棵樹(shù)的高度，使樹(shù)高始終保持為常數(shù)？
這樣每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)就是整棵樹(shù)的根節(jié)點(diǎn)，find就能以 O(1) 的時(shí)間找到某一節(jié)點(diǎn)的根節(jié)點(diǎn)，相應(yīng)的，connected和union復(fù)雜度都下降為 O(1)。
要做到這一點(diǎn)主要是修改find函數(shù)邏輯，非常簡(jiǎn)單，但你可能會(huì)看到兩種不同的寫(xiě)法。
第一種是在find中加一行代碼：
?
?
private?int?find(int?x)?{
????while?(parent[x]?!=?x)?{
????????//?這行代碼進(jìn)行路徑壓縮
????????parent[x]?=?parent[parent[x]];
????????x?=?parent[x];
????}
????return?x;
}
?
?
這個(gè)操作有點(diǎn)匪夷所思，看個(gè) GIF 就明白它的作用了（為清晰起見(jiàn)，這棵樹(shù)比較極端）：
用語(yǔ)言描述就是，每次 while 循環(huán)都會(huì)把一對(duì)兒父子節(jié)點(diǎn)改到同一層，這樣每次調(diào)用find函數(shù)向樹(shù)根遍歷的同時(shí)，順手就將樹(shù)高縮短了。
路徑壓縮的第二種寫(xiě)法是這樣：
?
?
//?第二種路徑壓縮的?find?方法
public?int?find(int?x)?{
????if?(parent[x]?!=?x)?{
????????parent[x]?=?find(parent[x]);
????}
????return?parent[x];
}
?
?
我一度認(rèn)為這種遞歸寫(xiě)法和第一種迭代寫(xiě)法做的事情一樣，但實(shí)際上是我大意了，有讀者指出這種寫(xiě)法進(jìn)行路徑壓縮的效率是高于上一種解法的。
這個(gè)遞歸過(guò)程有點(diǎn)不好理解，你可以自己手畫(huà)一下遞歸過(guò)程。我把這個(gè)函數(shù)做的事情翻譯成迭代形式，方便你理解它進(jìn)行路徑壓縮的原理：
?
?
//?這段迭代代碼方便你理解遞歸代碼所做的事情
public?int?find(int?x)?{
????//?先找到根節(jié)點(diǎn)
????int?root?=?x;
????while?(parent[root]?!=?root)?{
????????root?=?parent[root];
????}
????//?然后把?x?到根節(jié)點(diǎn)之間的所有節(jié)點(diǎn)直接接到根節(jié)點(diǎn)下面
????int?old_parent?=?parent[x];
????while?(x?!=?root)?{
????????parent[x]?=?root;
????????x?=?old_parent;
????????old_parent?=?parent[old_parent];
????}
????return?root;
}
?
?
這種路徑壓縮的效果如下：
比起第一種路徑壓縮，顯然這種方法壓縮得更徹底，直接把一整條樹(shù)枝壓平，一點(diǎn)意外都沒(méi)有。就算一些極端情況下產(chǎn)生了一棵比較高的樹(shù)，只要一次路徑壓縮就能大幅降低樹(shù)高，從?攤還分析?的角度來(lái)看，所有操作的平均時(shí)間復(fù)雜度依然是 O(1)，所以從效率的角度來(lái)說(shuō)，推薦你使用這種路徑壓縮算法。
另外，如果使用路徑壓縮技巧，那么size數(shù)組的平衡優(yōu)化就不是特別必要了。所以你一般看到的 Union Find 算法應(yīng)該是如下實(shí)現(xiàn)：
?
?
class?UF?{
????//?連通分量個(gè)數(shù)
????private?int?count;
????//?存儲(chǔ)每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)
????private?int[]?parent;
????//?n?為圖中節(jié)點(diǎn)的個(gè)數(shù)
????public?UF(int?n)?{
????????this.count?=?n;
????????parent?=?new?int[n];
????????for?(int?i?=?0;?i?
?
?
Union-Find 算法的復(fù)雜度可以這樣分析：構(gòu)造函數(shù)初始化數(shù)據(jù)結(jié)構(gòu)需要 O(N) 的時(shí)間和空間復(fù)雜度；連通兩個(gè)節(jié)點(diǎn)union、判斷兩個(gè)節(jié)點(diǎn)的連通性connected、計(jì)算連通分量count所需的時(shí)間復(fù)雜度均為 O(1)。
到這里，相信你已經(jīng)掌握了 Union-Find 算法的核心邏輯，總結(jié)一下我們優(yōu)化算法的過(guò)程：
1、用parent數(shù)組記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，相當(dāng)于指向父節(jié)點(diǎn)的指針，所以parent數(shù)組內(nèi)實(shí)際存儲(chǔ)著一個(gè)森林（若干棵多叉樹(shù)）。
2、用size數(shù)組記錄著每棵樹(shù)的重量，目的是讓union后樹(shù)依然擁有平衡性，保證各個(gè) API 時(shí)間復(fù)雜度為 O(logN)，而不會(huì)退化成鏈表影響操作效率。
3、在find函數(shù)中進(jìn)行路徑壓縮，保證任意樹(shù)的高度保持在常數(shù)，使得各個(gè) API 時(shí)間復(fù)雜度為 O(1)。使用了路徑壓縮之后，可以不使用size數(shù)組的平衡優(yōu)化。
下面我們看一些具體的并查集題目。
題目實(shí)踐
力扣第 323 題「無(wú)向圖中連通分量的數(shù)目」就是最基本的連通分量題目：
給你輸入一個(gè)包含n個(gè)節(jié)點(diǎn)的圖，用一個(gè)整數(shù)n和一個(gè)數(shù)組edges表示，其中edges[i] = [ai, bi]表示圖中節(jié)點(diǎn)ai和bi之間有一條邊。請(qǐng)你計(jì)算這幅圖的連通分量個(gè)數(shù)。
函數(shù)簽名如下：
?
?
int?countComponents(int?n,?int[][]?edges)
?
?
這道題我們可以直接套用UF類(lèi)來(lái)解決：
?
?
public?int?countComponents(int?n,?int[][]?edges)?{
????UF?uf?=?new?UF(n);
????//?將每個(gè)節(jié)點(diǎn)進(jìn)行連通
????for?(int[]?e?:?edges)?{
????????uf.union(e[0],?e[1]);
????}
????//?返回連通分量的個(gè)數(shù)
????return?uf.count();
}
class?UF?{
????//?見(jiàn)上文
}
?
?
另外，一些使用 DFS 深度優(yōu)先算法解決的問(wèn)題，也可以用 Union-Find 算法解決。
比如力扣第 130 題「被圍繞的區(qū)域」：
給你一個(gè) M×N 的二維矩陣，其中包含字符X和O，讓你找到矩陣中四面被X圍住的O，并且把它們替換成X。
?
?
void?solve(char[][]?board);
?
?
注意哦，必須是四面被圍的O才能被換成X，也就是說(shuō)邊角上的O一定不會(huì)被圍，進(jìn)一步，與邊角上的O相連的O也不會(huì)被X圍四面，也不會(huì)被替換。
PS：這讓我想起小時(shí)候玩的棋類(lèi)游戲「黑白棋」，只要你用兩個(gè)棋子把對(duì)方的棋子夾在中間，對(duì)方的子就被替換成你的子?？梢?jiàn)，占據(jù)四角的棋子是無(wú)敵的，與其相連的邊棋子也是無(wú)敵的（無(wú)法被夾掉）。
其實(shí)這個(gè)問(wèn)題應(yīng)該歸為?島嶼系列問(wèn)題?使用 DFS 算法解決：
先用 for 循環(huán)遍歷棋盤(pán)的四邊，用 DFS 算法把那些與邊界相連的O換成一個(gè)特殊字符，比如#；然后再遍歷整個(gè)棋盤(pán)，把剩下的O換成X，把#恢復(fù)成O。這樣就能完成題目的要求，時(shí)間復(fù)雜度 O(MN)。
但這個(gè)問(wèn)題也可以用 Union-Find 算法解決，雖然實(shí)現(xiàn)復(fù)雜一些，甚至效率也略低，但這是使用 Union-Find 算法的通用思想，值得一學(xué)。
你可以把那些不需要被替換的O看成一個(gè)擁有獨(dú)門(mén)絕技的門(mén)派，它們有一個(gè)共同「祖師爺」叫dummy，這些O和dummy互相連通，而那些需要被替換的O與dummy不連通。
這就是 Union-Find 的核心思路，明白這個(gè)圖，就很容易看懂代碼了。
首先要解決的是，根據(jù)我們的實(shí)現(xiàn)，Union-Find 底層用的是一維數(shù)組，構(gòu)造函數(shù)需要傳入這個(gè)數(shù)組的大小，而題目給的是一個(gè)二維棋盤(pán)。
這個(gè)很簡(jiǎn)單，二維坐標(biāo)(x,y)可以轉(zhuǎn)換成x * n + y這個(gè)數(shù)（m是棋盤(pán)的行數(shù)，n是棋盤(pán)的列數(shù)），敲黑板，這是將二維坐標(biāo)映射到一維的常用技巧。
其次，我們之前描述的「祖師爺」是虛構(gòu)的，需要給他老人家留個(gè)位置。索引[0.. m*n-1]都是棋盤(pán)內(nèi)坐標(biāo)的一維映射，那就讓這個(gè)虛擬的dummy節(jié)點(diǎn)占據(jù)索引m * n好了。
看解法代碼：
?
?
void?solve(char[][]?board)?{
????if?(board.length?==?0)?return;
????int?m?=?board.length;
????int?n?=?board[0].length;
????//?給?dummy?留一個(gè)額外位置
????UF?uf?=?new?UF(m?*?n?+?1);
????int?dummy?=?m?*?n;
????//?將首列和末列的?O?與?dummy?連通
????for?(int?i?=?0;?i?
?
?
這段代碼很長(zhǎng)，其實(shí)就是剛才的思路實(shí)現(xiàn)，只有和邊界O相連的O才具有和dummy的連通性，他們不會(huì)被替換。
其實(shí)用 Union-Find 算法解決這個(gè)簡(jiǎn)單的問(wèn)題有點(diǎn)殺雞用牛刀，它可以解決更復(fù)雜，更具有技巧性的問(wèn)題，主要思路是適時(shí)增加虛擬節(jié)點(diǎn)，想辦法讓元素「分門(mén)別類(lèi)」，建立動(dòng)態(tài)連通關(guān)系。
力扣第 990 題「等式方程的可滿足性」用 Union-Find 算法就顯得十分優(yōu)美了，題目是這樣：
給你一個(gè)數(shù)組equations，裝著若干字符串表示的算式。每個(gè)算式equations[i]長(zhǎng)度都是 4，而且只有這兩種情況：a==b或者a!=b，其中a,b可以是任意小寫(xiě)字母。你寫(xiě)一個(gè)算法，如果equations中所有算式都不會(huì)互相沖突，返回 true，否則返回 false。
比如說(shuō)，輸入["a==b","b!=c","c==a"]，算法返回 false，因?yàn)檫@三個(gè)算式不可能同時(shí)正確。
再比如，輸入["c==c","b==d","x!=z"]，算法返回 true，因?yàn)檫@三個(gè)算式并不會(huì)造成邏輯沖突。
我們前文說(shuō)過(guò)，動(dòng)態(tài)連通性其實(shí)就是一種等價(jià)關(guān)系，具有「自反性」「?jìng)鬟f性」和「對(duì)稱性」，其實(shí)==關(guān)系也是一種等價(jià)關(guān)系，具有這些性質(zhì)。所以這個(gè)問(wèn)題用 Union-Find 算法就很自然。
核心思想是，將equations中的算式根據(jù)==和!=分成兩部分，先處理==算式，使得他們通過(guò)相等關(guān)系各自勾結(jié)成門(mén)派（連通分量）；然后處理!=算式，檢查不等關(guān)系是否破壞了相等關(guān)系的連通性。
?
?
boolean?equationsPossible(String[]?equations)?{
????//?26?個(gè)英文字母
????UF?uf?=?new?UF(26);
????//?先讓相等的字母形成連通分量
????for?(String?eq?:?equations)?{
????????if?(eq.charAt(1)?==?'=')?{
????????????char?x?=?eq.charAt(0);
????????????char?y?=?eq.charAt(3);
????????????uf.union(x?-?'a',?y?-?'a');
????????}
????}
????//?檢查不等關(guān)系是否打破相等關(guān)系的連通性
????for?(String?eq?:?equations)?{
????????if?(eq.charAt(1)?==?'!')?{
????????????char?x?=?eq.charAt(0);
????????????char?y?=?eq.charAt(3);
????????????//?如果相等關(guān)系成立，就是邏輯沖突
????????????if?(uf.connected(x?-?'a',?y?-?'a'))
????????????????return?false;
????????}
????}
????return?true;
}
class?UF?{
????//?見(jiàn)上文
}
?
?
至此，這道判斷算式合法性的問(wèn)題就解決了，借助 Union-Find 算法，是不是很簡(jiǎn)單呢？
最后，Union-Find 算法也會(huì)在一些其他經(jīng)典圖論算法中用到，比如判斷「圖」和「樹(shù)」，以及最小生成樹(shù)的計(jì)算，詳情見(jiàn)?Kruskal 最小生成樹(shù)算法。
編輯：黃飛
?
工商網(wǎng)監(jiān)
評(píng)論