1 并查集介紹

????????并查集主要用于解決一些元素分組的問(wèn)題。它管理一系列不相交的集合，并支持兩種操作：

• 合并（Union）：把兩個(gè)不相交的集合合并為一個(gè)集合。
• 查詢（Find）：查詢兩個(gè)元素是否在同一個(gè)集合中。

2 用比武的方式解釋并查集

????????并查集的重要思想在于，用集合中的一個(gè)元素代表集合。我們不妨把集合比喻成幫派，而代表元素則是幫主。

????????接下來(lái)我們利用這個(gè)比喻，看看并查集是如何運(yùn)作的。

????????最開始，所有大俠各自為戰(zhàn)。他們各自的幫主自然就是自己。（對(duì)于只有一個(gè)元素的集合，代表元素自然是唯一的那個(gè)元素）

????????現(xiàn)在1號(hào)和3號(hào)比武，假設(shè)1號(hào)贏了（這里具體誰(shuí)贏暫時(shí)不重要），那么3號(hào)就認(rèn)1號(hào)作幫主（合并1號(hào)和3號(hào)所在的集合，1號(hào)為代表元素）。???????

?

????????現(xiàn)在2號(hào)想和3號(hào)比武（合并3號(hào)和2號(hào)所在的集合），但3號(hào)表示，別跟我打，讓我?guī)椭鱽?lái)收拾你（合并代表元素）。不妨設(shè)這次又是1號(hào)贏了，那么2號(hào)也認(rèn)1號(hào)做幫主。

?

?現(xiàn)在我們假設(shè)4、5、6號(hào)也進(jìn)行了一番幫派合并，江湖局勢(shì)變成下面這樣：

?現(xiàn)在假設(shè)2號(hào)想與6號(hào)比，跟剛剛說(shuō)的一樣，喊幫主1號(hào)和4號(hào)出來(lái)打一架【小弟約架，幫主出面】。1號(hào)勝利后，4號(hào)認(rèn)1號(hào)為幫主，當(dāng)然他的手下也都是跟著投降了。?

? ? ? ? 不難發(fā)現(xiàn)，這是一個(gè)樹狀的結(jié)構(gòu)，要尋找集合的代表元素，只需要一層一層往上訪問(wèn)父節(jié)點(diǎn)（圖中箭頭所指的圓），直達(dá)樹的根節(jié)點(diǎn)（圖中橙色的圓）即可。根節(jié)點(diǎn)的父節(jié)點(diǎn)是它自己。我們可以直接把它畫成一棵樹：

?3 原始并查集代碼部分

假設(shè)我們有5個(gè)點(diǎn)

3.1 初始化

naive_union_find=[0] for i in range(1,5+1):naive_union_find.append(i) naive_union_find ''' [0, 1, 2, 3, 4, 5] '''

????????假如有編號(hào)為1, 2, 3, 4, 5的5個(gè)元素，我們用一個(gè)數(shù)組naive_union_find來(lái)存儲(chǔ)每個(gè)元素的父節(jié)點(diǎn)（因?yàn)槊總€(gè)元素有且只有一個(gè)父節(jié)點(diǎn)，所以這是可行的）。

????????一開始，我們先將它們的父節(jié)點(diǎn)設(shè)為自己。

? ? ? ? 假設(shè)有n個(gè)點(diǎn)，那么初始化操作的時(shí)間復(fù)雜度是O(n)

3.2 查詢

? ? ? ? 查找一個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)（也就是這個(gè)節(jié)點(diǎn)屬于哪個(gè)“幫派”）

def find(x):if(naive_union_find[x]=x):return xelse:return find(naive_union_find[x])

????????我們用遞歸的寫法實(shí)現(xiàn)對(duì)代表元素的查詢：一層一層訪問(wèn)父節(jié)點(diǎn)，直至根節(jié)點(diǎn)（根節(jié)點(diǎn)的標(biāo)志就是父節(jié)點(diǎn)是本身）。

????????要判斷兩個(gè)元素是否屬于同一個(gè)集合，只需要看它們的根節(jié)點(diǎn)是否相同即可。

????????假設(shè)有n個(gè)點(diǎn)，那么合并操作的時(shí)間復(fù)雜度是O(樹的深度)【從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)層層遍歷上去】

? ? ? ?定理：在并查集中，?假設(shè)有n個(gè)點(diǎn)，那么樹的最大深度為O(logn)

? ? ? ? 證明：

當(dāng)包含u的集合被合并了之后，整體并查集樹的深度最多增加1（在5.2節(jié)我們會(huì)知道，只有合并的兩棵并查集樹深度一樣的時(shí)候，整體并查集樹的深度才會(huì)增加1）

因?yàn)槲覀兌际巧疃刃〉臉渫疃却蟮臄?shù)合并，所以如果深度增加的話，整體并查集數(shù)的節(jié)點(diǎn)數(shù)量至少翻倍

節(jié)點(diǎn)的數(shù)量是n，所以層數(shù)最多O(logn)

? ? ? ? ?所以，此時(shí)查詢操作的時(shí)間復(fù)雜度是O(logn)

3.3 合并

def merge(i,j):naive_union_find[find(i)]=find(j)

????????合并操作也是很簡(jiǎn)單的，先找到兩個(gè)集合的代表元素，然后將前者的父節(jié)點(diǎn)設(shè)為后者即可。????????

????????當(dāng)然也可以將后者的父節(jié)點(diǎn)設(shè)為前者，這里暫時(shí)不重要。之后會(huì)給出一個(gè)更合理的比較方法。?

?????????假設(shè)有n個(gè)點(diǎn)，那么合并操作的時(shí)間復(fù)雜度是O(1)

?4 路徑壓縮

最簡(jiǎn)單的并查集效率是比較低的。例如，來(lái)看下面這個(gè)場(chǎng)景：

現(xiàn)在我們要merge(2,3)，于是從2找到1，naive_union_find[1]=3，于是變成了這樣：

?

?然后我們又找來(lái)一個(gè)元素4，并需要執(zhí)行merge(2,4)：

?

從2找到1，再找到3，然后naive_union_find[3]=4，于是變成了這樣：

?

?這樣可能會(huì)形成一條長(zhǎng)長(zhǎng)的鏈，隨著鏈越來(lái)越長(zhǎng)，我們想要從底部找到根節(jié)點(diǎn)會(huì)變得越來(lái)越難。

?怎么解決呢？我們可以使用路徑壓縮的方法。既然我們只關(guān)心一個(gè)元素對(duì)應(yīng)的根節(jié)點(diǎn)，那我們希望每個(gè)元素到根節(jié)點(diǎn)的路徑盡可能短，最好只需要一步，像這樣：

?其實(shí)這說(shuō)來(lái)也很好實(shí)現(xiàn)。只要我們?cè)诓樵兊倪^(guò)程中，把沿途的每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)都設(shè)為根節(jié)點(diǎn)即可。下一次再查詢時(shí)，我們就可以省很多事。這用遞歸的寫法很容易實(shí)現(xiàn)：

def find(x):if(naive_union_find[x]=x):return xelse:#return find(naive_union_find[x]) 原來(lái)的查詢naive_union_find[x]=find(naive_union_find[x])#將目前節(jié)點(diǎn)的父節(jié)點(diǎn)直接設(shè)置為根節(jié)點(diǎn)return(naive_union_find[x])#返回當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，也就是根節(jié)點(diǎn)

?????????路徑壓縮優(yōu)化后，并查集的時(shí)間復(fù)雜度已經(jīng)比較低了，絕大多數(shù)不相交集合的合并查詢問(wèn)題都能夠解決。然而，對(duì)于某些時(shí)間卡得很緊的題目，我們還可以進(jìn)一步優(yōu)化。

????????有些人可能有一個(gè)誤解，以為路徑壓縮優(yōu)化后，并查集始終都是一個(gè)菊花圖（只有兩層的樹的俗稱）。但其實(shí)，由于路徑壓縮只在查詢時(shí)進(jìn)行，也只壓縮一條路徑，所以并查集最終的結(jié)構(gòu)仍然可能是比較復(fù)雜的。

4.1 路徑壓縮的效率提升

? ? ? ? 直接看結(jié)論吧：使用路徑壓縮之后，Find操作的平均時(shí)長(zhǎng)為O(α(n))，其中α(n)是阿克曼函數(shù)（Ackermann function ）A(n,n)的倒數(shù)

?4.1.2 阿克曼函數(shù)

? ? ? ? 阿克曼函數(shù)的定義如下：

這是一個(gè)增長(zhǎng)速度很快的函數(shù)

????????而使用路徑壓縮之后，Find操作的平均時(shí)間復(fù)雜度是O(α(n))，，其中α(n)是阿克曼函數(shù)（Ackermann function ）A(n,n)的倒數(shù)。所以是一個(gè)很小的數(shù)。（經(jīng)驗(yàn)結(jié)論，對(duì)于一般的數(shù)據(jù)集來(lái)說(shuō)，α(n)≤5）

5 按秩合并

現(xiàn)在我們有一棵較復(fù)雜的樹需要與一個(gè)單元素的集合合并

????????假如這時(shí)我們要merge(7,8)，如果我們可以選擇的話，是把7的父節(jié)點(diǎn)設(shè)為8好，還是把8的父節(jié)點(diǎn)設(shè)為7好呢？

????????

????????當(dāng)然是后者。因?yàn)槿绻?的父節(jié)點(diǎn)設(shè)為8，會(huì)使樹的深度（樹中最長(zhǎng)鏈的長(zhǎng)度）加深，原來(lái)的樹中每個(gè)元素到根節(jié)點(diǎn)的距離都變長(zhǎng)了，之后我們尋找根節(jié)點(diǎn)的路徑也就會(huì)相應(yīng)變長(zhǎng)。雖然我們有路徑壓縮，但路徑壓縮也是會(huì)消耗時(shí)間的。而把8的父節(jié)點(diǎn)設(shè)為7，則不會(huì)有這個(gè)問(wèn)題，因?yàn)樗鼪]有影響到不相關(guān)的節(jié)點(diǎn)。?

????????這啟發(fā)我們：我們應(yīng)該把簡(jiǎn)單的樹往復(fù)雜的樹上合并，而不是相反。因?yàn)檫@樣合并后，到根節(jié)點(diǎn)距離變長(zhǎng)的節(jié)點(diǎn)個(gè)數(shù)比較少。

????????我們用一個(gè)數(shù)組rank[]記錄每個(gè)根節(jié)點(diǎn)對(duì)應(yīng)的樹的深度（如果不是根節(jié)點(diǎn)，其rank相當(dāng)于以它作為根節(jié)點(diǎn)的子樹的深度）。

????????一開始，把所有元素的rank（秩）設(shè)為1。合并時(shí)比較兩個(gè)根節(jié)點(diǎn)，把rank較小者往較大者上合并。

? 5.1 初始化（按秩合并）

naive_union_find=[0] #記錄每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的父節(jié)點(diǎn) rank_union_find=[0] #記錄每個(gè)節(jié)點(diǎn)的秩 for i in range(1,5+1):naive_union_find.append(i)rank_union_find.append(1)

5.2 合并（按秩合并）

def merge(i,j):i=find(i)j=find(j)if(rank_union_find[i]>rank_union_find[j]):naive_union_find[j]=ielse:naive_union_find[i]=jif(rank_union_find[i]==rank_union_find[j] and i!=j):rank[j]+=1#如果深度相同，但是根節(jié)點(diǎn)不同，那么新的根節(jié)點(diǎn)的深度+1#因?yàn)槿绻瓉?lái)的深度不同的話，合并之后根節(jié)點(diǎn)的深度不會(huì)增加（因?yàn)槭切〉暮喜⒌蕉嗟?#xff09;

????????為什么深度相同，新的根節(jié)點(diǎn)深度要+1？

????????如下圖，我們有兩個(gè)深度均為2的樹，現(xiàn)在要merge(2,5)：

????????這里把2的父節(jié)點(diǎn)設(shè)為5，或者把5的父節(jié)點(diǎn)設(shè)為2，其實(shí)沒有太大區(qū)別。我們選擇前者，于是變成這樣：

????????

?????????顯然樹的深度增加了1。另一種合并方式同樣會(huì)讓樹的深度+1。

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的算法笔记：并查集的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。