前言
看了下時(shí)間距離上一篇 線性表 的文章已經(jīng)過去了半年了……
雖然這段時(shí)間倒也沒有停止學(xué)習(xí)，但也由于各種原因總之是一直拖著沒產(chǎn)出往衷。所幸最近因?yàn)橐恍C(jī)緣巧合杠上了并查集，趁熱打鐵的趕緊把這篇文章寫了黑忱。
考慮到自己學(xué)習(xí)這些東西的過程其實(shí)也不是線性的（總是忍不住東搞搞西搞搞），所以這篇就以更加輕松的方式來簡單分享一下最近對并查集這種數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)好了。
0.1 關(guān)于并查集
其實(shí)早在我寫 數(shù)據(jù)結(jié)構(gòu)其一 線性表 一文之前就已經(jīng)自己寫了一個(gè)簡單的并查集類實(shí)現(xiàn) yuchiXiong/data-structure-and-algorithm/commit/ae60aa61c4e4581be3b5508e8887f1f7331b53e7 了甫煞，當(dāng)時(shí)剛開始看 《算法（第 4 版）》菇曲，書的第一章結(jié)尾用并查集做了簡單的案例。
打開這段代碼的時(shí)候抚吠，就發(fā)現(xiàn)文件頭寫了三行注釋常潮，很好的說明了我當(dāng)時(shí)寫完這個(gè)代碼的心境：
/**
* ! 對于這個(gè)數(shù)據(jù)結(jié)構(gòu)的疑問
* 1. 給定的數(shù)據(jù)一定是有序的嗎？find 函數(shù)越界問題
* 2. 使用場景
*/
另外從代碼中也發(fā)現(xiàn)了不少 Bug楷力，反思了一下覺得自己一直不肯寫這篇的一大原因可能是沒有理解喊式。
0.2 Why again?
故事要從本月 18 號的 LeetCode 每日一題 LC27. 最大人工島 說起了。
作為一個(gè)算法廢人弥雹，我一直是 “困難唯唯諾諾垃帅，簡單重拳出擊” 的擺爛心態(tài)延届，此外我一直堅(jiān)信一件事情：
當(dāng)你看完一個(gè)算法題 5 分鐘內(nèi)一點(diǎn)思路都沒有剪勿，那大概率是因?yàn)槟氵€不具備解決該類問題的知（suan）識（fa）儲（tao）備（lu），而非你腦子有問題/狗頭
但好巧不巧方庭，在 LeetCode 數(shù)據(jù)結(jié)構(gòu)入門的專題訓(xùn)練中厕吉，有一道 LC695. 島嶼的最大面積。
這道題的思路很簡單械念，由于每一個(gè)島嶼單元所處的島嶼面積一定等于它上下左右四個(gè)方向鄰接單元上的島嶼面積之和头朱，很容易寫出 DFS 的代碼模板。
當(dāng)然龄减，要記得定義遞歸的終止條件项钮，即如果當(dāng)前單元為 0 時(shí)，意味著已經(jīng)遍歷到海洋了希停，不需要繼續(xù)了烁巫。另外為了防止重復(fù)遍歷，代碼還對已經(jīng)遍歷過的島嶼進(jìn)行了標(biāo)記宠能。
代碼見 yuchiXiong/data-structure-and-algorithm/commit/63659b20643b1e6b7b8bfb59efd283d21257868a
顯而易見的事情是 LC27. 最大人工島 的一種暴力解法就是嘗試將地圖上的每一片海洋都改成島嶼然后求得最大島嶼面積亚隙，最終得到的最大值就是題解。
雖然不能保證效率违崇，但能暴力解決的問題都不是問題/再次狗頭阿弃，開整。
在經(jīng)過了一段時(shí)間的死嗑之后羞延，我寫下了這段代碼：
/**
* @param {number[][]} grid
* @return {number}
*/
const largestIsland = function (grid) {
let count = 2;
let max = maxAreaOfIsland(grid, count++);
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
// 跳過島嶼渣淳，我們只對海洋做操作
if (grid[i][j] !== 0) {
continue;
}
// 嘗試檢測當(dāng)前海洋的四面是否存在島嶼伴箩，如果四面都沒有島嶼入愧，則當(dāng)前人工島面積為 1
if (tryDFS(grid, i, j) === 0) {
max = max < 1 ? 1 : max;
continue;
}
// 修改當(dāng)前單元 海洋->島嶼 并求得最大島嶼面積
const origin = grid[i][j];
grid[i][j] = 1;
const cur = maxAreaOfIsland(grid, count++);
max = max < cur ? cur : max;
grid[i][j] = origin;
}
}
return max;
};
/**
* @param {number[][]} grid
* @param {number} count
* @return {number}
*/
var maxAreaOfIsland = function (grid, count) {
let max = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
if (grid[i][j] === 1) {
max = Math.max(max, dfs(grid, i, j, count));
}
}
}
return max;
};
/**
* @param {number[][]} grid
* @param {number} i
* @param {number} j
* @param {number} count
* @return {number}
*/
const dfs = (grid, i, j, count) => {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return 0;
if (grid[i][j] === 0 || grid[i][j] === count) return 0;
grid[i][j] = count;
return 1
+ dfs(grid, i - 1, j, count)
+ dfs(grid, i + 1, j, count)
+ dfs(grid, i, j - 1, count)
+ dfs(grid, i, j + 1, count);
}
/**
* 返回當(dāng)前單元四個(gè)方向范圍內(nèi)的島嶼面積總和
* @param {number[][]} grid
* @param {number} i
* @param {number} j
* @return {number}
*/
const tryDFS = (grid, i, j) => {
return (i >= 1 ? (grid[i - 1][j]) : 0)
+ (i < grid.length - 1 ? grid[i + 1][j] : 0)
+ (j >= 1 ? grid[i][j - 1] : 0)
+ (j < grid[i].length - 1 ? grid[i][j + 1] : 0);
}
其中maxAreaOfIsland函數(shù)是直接復(fù)制的 LC695. 島嶼的最大面積 的答案。
需要解釋的幾點(diǎn)：
- 前面提到在 DFS 過程中會標(biāo)記已經(jīng)遍歷過的島嶼，也就是說每一次
maxAreaOfIsland后grid數(shù)組中的島嶼標(biāo)識會由 1 變成 2砂客，為了使程序能夠繼續(xù)執(zhí)行第二輪maxAreaOfIsland泥张，需要將grid數(shù)組復(fù)原，但這樣的又會增加相當(dāng)大的開銷鞠值，于是最終我將函數(shù)改成了上面的版本媚创，每次傳入一個(gè)count變量來標(biāo)識輪次，這樣 DFS 也能重復(fù)執(zhí)行了彤恶； - 為了盡可能提高效率钞钙，程序首先跳過了島嶼單元，然后對四周都沒有島嶼的單元做了提前處理声离，詳見注釋芒炼；
在完成了一些簡單的優(yōu)化后，一些之前不能通過的 case 也能跑出一個(gè)可以接受的執(zhí)行時(shí)間了术徊，但最終還是卡在了 case70 上本刽。
在對這個(gè) case 進(jìn)行了簡單的分析之后我發(fā)現(xiàn)：
- 這是一個(gè) 417*417 規(guī)模的數(shù)組；
- 島嶼和海洋的數(shù)量幾乎相同赠涮；
- 島嶼與海洋的分布稀疏子寓；
不難發(fā)現(xiàn)上述優(yōu)化策略很難產(chǎn)生效果。
本來這題就該到此為止了笋除，畢竟死磕沒有意義斜友，又不能說服自己 “答案是對的，只是超時(shí)了而已”垃它。
然而接下來一個(gè)不經(jīng)意的操作鲜屏，讓我發(fā)現(xiàn)了這一題的相關(guān)標(biāo)簽中赫然寫著一個(gè)并查集。
如果是我沒有接觸過的東西那倒也罷了国拇，一個(gè)我手寫過的東西為什么能把我困茁迨贰？
1. 并查集
既然這是一篇分享并查集的博客贝奇，那么還是有必要介紹一下并查集的虹菲。
從字面上來看，并查集是一種集合數(shù)據(jù)結(jié)構(gòu)掉瞳，它主要定義了聯(lián)合（union）和查詢（find）兩種操作毕源，因此很多時(shí)候也被叫做 UnionFind。
wiki：并查集
查詢：查詢某個(gè)元素屬于哪個(gè)集合陕习，通常是返回集合內(nèi)的一個(gè) “代表元素”霎褐。這個(gè)操作是為了判斷兩個(gè)元素是否在同一個(gè)集合之中。
合并：將兩個(gè)集合合并為一個(gè)该镣。
添加：添加一個(gè)新集合冻璃，其中有一個(gè)新元素。添加操作不如查詢和合并操作重要，常常被忽略省艳。
并查集定義的查詢操作能夠快速的反應(yīng)集合中兩個(gè)元素的連通性娘纷，而合并/聯(lián)合操作則可以將集合中的兩個(gè)元素連通，它被廣泛的應(yīng)用在動態(tài)連通性問題中跋炕。
對并查集應(yīng)用的一個(gè)簡單的例子就是族譜赖晶，設(shè)想我們?nèi)绾闻袛鄡蓚€(gè)人 A 和 B 是否來自于同一個(gè)家族？
一個(gè)簡單的方法就是向上溯源辐烂，如果 A 和 B 的長輩中有同一人遏插，則我們可以認(rèn)為這兩個(gè)人來自同一個(gè)家族。
將問題的規(guī)模擴(kuò)展到三人纠修，如果我們當(dāng)前已經(jīng)知曉 A 和 B 來自同一個(gè)家族胳嘲，則我們只需要證明第三人 C 與 A/B 任意一人來自同一個(gè)家族，就可以認(rèn)為 C 與另外一人來自同一個(gè)家族扣草。
由此我們可以得到并查集中元素的三個(gè)重要性質(zhì)：
- 自反性了牛，A 和 A 是連通的；
- 對稱性德召，如果 A 和 B 是連通的白魂，那么 B 和 A 也是連通的；
- 傳遞性上岗，如果 A 和 B 是連通的且 B 和 C 是連通的，那么 A 和 C 也是連通的蕴坪。
2. 并查集的實(shí)現(xiàn)
只提概念不談實(shí)現(xiàn)是沒有意義的肴掷。
并查集的主要操作有兩個(gè)，查詢和合并背传，實(shí)現(xiàn)這兩個(gè)方法是實(shí)現(xiàn)并查集最重要的部分呆瞻，除此之外在不同版本的并查集實(shí)現(xiàn)中往往存在著各種 API 定義上的差異，但數(shù)據(jù)結(jié)構(gòu)本身是用來解決程序問題的径玖，如果拘泥于 API 形式亦是有問題的痴脾，這個(gè)問題后面還會再提到。
在前面的例子里我們提到一個(gè)問題：如何判斷兩個(gè)人 A 和 B 是否來自于同一個(gè)家族梳星？
給出的答案很簡單：如果 A 和 B 的長輩中有同一人赞赖，則我們可以認(rèn)為這兩個(gè)人來自同一個(gè)家族。
在并查集的實(shí)現(xiàn)中我們亦可以這樣做冤灾。
在開始之前前域，我們要簡單分析一下上面的描述，在這個(gè)系統(tǒng)里存在一種父子關(guān)系韵吨，且多個(gè)元素可能有一個(gè)共同的根元素匿垄，很顯然，沒有比樹更合適的數(shù)據(jù)結(jié)構(gòu)了。
當(dāng)然椿疗，并查集具有檢測兩個(gè)元素是否連通的能力漏峰，也就意味著在并查集中可能存在多個(gè)沒有交集的樹，因此我們更進(jìn)一步的表達(dá)為森林這樣一種數(shù)據(jù)結(jié)構(gòu)届榄。
2.1 構(gòu)建一個(gè)并查集
實(shí)現(xiàn)一個(gè)基本的并查集需要一個(gè)合適的變量來存儲森林這種結(jié)構(gòu)芽狗，前面在 線性表 一文中提到過，無論邏輯呈現(xiàn)什么樣的結(jié)構(gòu)痒蓬，在計(jì)算機(jī)存儲時(shí)都只有線性存儲與鏈?zhǔn)酱鎯煞N童擎。這里一樣擁有這種自由，《算法（第 4 版）》 中使用了順序結(jié)構(gòu)攻晒。
使用順序表實(shí)現(xiàn)森林時(shí)首先將并查集中的所有元素的值作為 key 創(chuàng)建一個(gè)順序表（姑且不去討論元素值類型與順序表下標(biāo)數(shù)值類型轉(zhuǎn)換的問題）顾复，在初始化時(shí)它的值是它自身，即當(dāng)前元素僅與自己連通鲁捏。
而后在每次進(jìn)行合并操作時(shí)芯砸，我們會修改元素的指向，類似下面這樣
trees[targetA] = targetB;
此時(shí)意味著元素 A 的父元素是元素 B给梅，同時(shí)以意味著元素 A 與元素 B 連通假丧。
2.1 查詢
就像家族關(guān)系的例子一樣，判斷兩個(gè)元素是否連通动羽，只需要判斷它們是否具有一個(gè)公共的根元素即可包帚。
基于上面 2.1 構(gòu)建的存儲結(jié)構(gòu)，找到根元素只需要不斷的向上查找运吓，一直找到到某一個(gè)自身與父元素相等的節(jié)點(diǎn)渴邦，這個(gè)元素就是整個(gè)樹的根元素。
function getRootNode(target)
{
while (trees[target] != target)
{
target = trees[target];
}
return target;
}
接下來的判斷就簡單了拘哨，當(dāng)getRootNode(elementA)與getRootNode(elementB)相同時(shí)谋梭，很顯然兩個(gè)元素是連通的。
2.2 合并
由上面的邏輯要實(shí)現(xiàn)合并也非常簡單倦青，不過在進(jìn)行兩個(gè)元素的合并之前首先要判斷是否連通瓮床，如果元素 A 和 B 已經(jīng)連通了，就沒有必要浪費(fèi)時(shí)間了产镐。
要進(jìn)行兩個(gè)元素的連通隘庄，只要把其中一方的父元素指向另一方就可以了，不過通常來說我們并不能得知當(dāng)前正在進(jìn)行連通的兩個(gè)元素是獨(dú)立的還是處于一個(gè)樹中磷账，貿(mào)然修改其指向有可能會使它脫離原來的樹峭沦，因此我們應(yīng)該對兩個(gè)樹的根元素進(jìn)行操作。
簡單的參考代碼如下：
function unionNode(a, b)
{
const parentA = getRootNode(a);
const parentB = getRootNode(b);
if (parentA == parentB)
return;
parent[parentB] = parentA;
}
2.3 更進(jìn)一步
基本的實(shí)現(xiàn)其實(shí)到這里就已經(jīng)夠了逃糟，但設(shè)想這樣一種情況：
const uf = new UnionFind();
uf.union(1, 2);
uf.union(3, 2);
uf.union(4, 3);
uf.union(5, 4);
嘗試在紙上畫出這組 case 的連通過程吼鱼，很容易發(fā)現(xiàn)由于每一次構(gòu)建的過程中的元素 A 都是一個(gè)指向自身的只有一個(gè)節(jié)點(diǎn)的樹蓬豁，導(dǎo)致合并以后構(gòu)建的樹實(shí)際退化成了單鏈表。對于樹中任意一個(gè)節(jié)點(diǎn)要找到它的根元素菇肃，單鏈表的效率一定是低于一顆合理排布的樹的地粪。
優(yōu)化策略本質(zhì)上是要維護(hù)樹的平衡性，我們只需要在連接的過程中把更小的那顆樹連接到更大的那棵樹的根節(jié)點(diǎn)上琐谤，就可以盡可能保證樹的平衡性蟆技，也可以避免上述極端情況的發(fā)生。不過要實(shí)現(xiàn)這一步斗忌，我們需要增加一個(gè)類變量來記錄每一顆樹的大小质礼，以及在每一次連通的時(shí)候?qū)涞拇笮∵M(jìn)行累加。
相比二叉樹织阳，一個(gè)樹可以擁有的子節(jié)點(diǎn)數(shù)是沒有限制的眶蕉。如果一顆樹除根元素以外的所有元素均指向同一個(gè)根元素，即這棵樹只有兩層唧躲，那么除根元素以外的任意一個(gè)節(jié)點(diǎn)找到它的根元素都只需要向上查找一次造挽。
基于這個(gè)假設(shè)，我們可以在查找的過程中進(jìn)行路徑壓縮弄痹，使樹變得更加扁平化饭入。
理想情況下，所有元素都應(yīng)該直接連接在根元素下作為根元素的子節(jié)點(diǎn)肛真，下面代碼巧妙的實(shí)現(xiàn)了它：
function getRootNode(target) {
if (this.trees[target] !== target) {
this.trees[target] = this.getRootNode(this.trees[target]);
}
return this.trees[target];
}
為什么要在查找的過程中而不是在連通的過程中修改樹的結(jié)構(gòu)谐丢？
理想情況下，我們希望每個(gè)節(jié)點(diǎn)都直接鏈接到它的根節(jié)點(diǎn)上毁欣，但我們又不想像 quick-find 算法那樣通過修改大量鏈接做到這一點(diǎn)庇谆。我們接近這種理想狀態(tài)的方式很簡單，就是在檢查節(jié)點(diǎn)的同時(shí)將它們直接鏈接到根節(jié)點(diǎn)凭疮。這種方法乍一看很激進(jìn)，但它的實(shí)現(xiàn)非常容易串述，而且這些樹并沒有阻止我們進(jìn)行這種修改的特殊結(jié)構(gòu)：如果這么做能夠改進(jìn)算法的效率执解，我們就應(yīng)該實(shí)現(xiàn)它。
————《算法（第 4 版）》
至此我們實(shí)現(xiàn)了并查集數(shù)據(jù)結(jié)構(gòu)最重要的部分纲酗，可以看到的是它的代碼并不復(fù)雜衰腌，但又很好的給出了一個(gè)解決連通性問題的方案。
代碼參考 UnionFind.cpp
3. 回到島嶼上
我自然沒有忘記小島上還有問題等著我解決觅赊。
并查集中的每一個(gè)連通元素整體都被稱為一個(gè)連通分量右蕊，當(dāng)一個(gè)并查集中的所有元素都連通時(shí)，這個(gè)并查集只存在一個(gè)連通分量吮螺。
回到 LC695. 島嶼的最大面積 的問題中饶囚，如果把島嶼的每一個(gè)單元（即grid二維數(shù)組的每一個(gè)元素）看作并查集中的一個(gè)元素帕翻，則基于這組元素構(gòu)建的并查集中，一定包含連通分量數(shù)量 N 個(gè)島嶼萝风，其中最大面積的島嶼實(shí)際上就是最大連通分量的大小嘀掸。
去除了 DFS 的代碼基于并查集進(jìn)行了重新實(shí)現(xiàn)：
yuchiXiong/data-structure-and-algorithm/commit/445c5d669c468667ddfed32b921759cd586a815c
不得不吐槽的一件事情：代碼真的長了好多……
不過依然有一些地方值得留意：
- 在這一版代碼中，不再直接使用順序表來存儲父節(jié)點(diǎn)信息规惰，而是通過 Hash 表替代睬塌，這樣做的好處在于可以接受更多類型的 key；
- 把每一個(gè)元素在二維數(shù)組扁平化以后的序號作為并查集的元素歇万，
grid[i][j]在并查集中的 key 為(i - 1) * grid.length + j揩晴；
在解決這個(gè)問題時(shí)，并查集的優(yōu)點(diǎn)并沒有那么明顯贪磺，一定程度上來說代碼還顯得十分啰嗦硫兰，而在解決 LC27. 最大人工島 問題時(shí)，并查集帶來的收益就要明顯的多了缘挽。
使用地圖信息構(gòu)建一次并查集以后瞄崇，我們可以清晰的得知如下信息：
- 當(dāng)前地圖中的島嶼數(shù)量；
- 當(dāng)前地圖中的每一個(gè)單元所處島嶼的面積壕曼；
- 當(dāng)前地圖中任意兩個(gè)島嶼單元是否處于同一個(gè)島嶼中苏研；
利用這些信息，我們只需要遍歷地圖腮郊，在每一個(gè)海洋單元上計(jì)算它的上下左右四個(gè)單元所處的島嶼面積之和摹蘑，然后找到最大值即可得到題解。
當(dāng)然轧飞，如果上下左右四個(gè)鄰接單元有位于同一個(gè)島嶼的單元衅鹿，我們只計(jì)算一次。
yuchiXiong/data-structure-and-algorithm/commit/d8bbe157f7a07d881e7b06cee94e5a3a25a70d0a
至此过咬，兩道 LeetCode 問題也圓滿的解決了大渤。
4. 最后說兩句
重新審視了去年實(shí)現(xiàn)的代碼，除了注釋中的疑問外還有不少的 bug掸绞，于是趁著這個(gè)機(jī)會也一并修復(fù)了 Github: yuchiXiong/data-structure-and-algorithm/commit/e68b19772b57eaac4e49dba89f783266f0f9eef3泵三。
并查集是用來處理元素連通性問題的數(shù)據(jù)結(jié)構(gòu)，它僅僅關(guān)注元素與元素之間的連通問題衔掸，不關(guān)心森林用順序存儲還是鏈?zhǔn)酱鎯?shí)現(xiàn)烫幕。在合適的時(shí)間選擇合適的方法才是最重要的。
在查找一些并查集代碼實(shí)現(xiàn)的案例時(shí)敞映，會發(fā)現(xiàn)不同人寫下的代碼是不同的较曼，有的初始化時(shí)傳遞了連通分量來進(jìn)行，有的僅在使用時(shí)創(chuàng)建并進(jìn)行自連通振愿，但本質(zhì)上這些都是根據(jù)實(shí)際問題不同而自由發(fā)揮的捷犹。
另外一件值得一提的事情是弛饭，在嘗試找一些編程語言自帶的 DisjointSet 時(shí)，發(fā)現(xiàn) Ruby 的 Set 類中提供了一個(gè) disjoint?方法伏恐，當(dāng)兩個(gè)集合有相同的元素時(shí)孩哑，該方法返回 false，反之則返回 true翠桦。Set 是一種不會出現(xiàn)重復(fù)元素的數(shù)據(jù)結(jié)構(gòu)横蜒，并查集同樣是沒有交集的森林，如果把森林中的每個(gè)樹看作是一個(gè) Set销凑，僅僅一個(gè)函數(shù)就可以以完整的實(shí)現(xiàn)并查集的功能了丛晌。一方面我十分感嘆竟然可以通過如此簡單的方式實(shí)現(xiàn)并查集，同時(shí)另一方面則是更多的引人深思斗幼，數(shù)據(jù)結(jié)構(gòu)的 API 設(shè)計(jì)本就沒有標(biāo)準(zhǔn)可言澎蛛。
