今天是算法與數據結構的第18篇文章，我們一起來看一個經典的數據結構——並查集。
首先我們來解釋一下這個數據結構的名稱，並查集其實是一個縮寫，並指的是合併，查指的是查找，集自然就是集合。所以並查集的全稱是合併查找集合，那麼顧名思義，這是一個用來合併、查找集合的數據結構。
並查集的定義
集合雖然是一個抽象的概念，但是生活當中關於集合的操作其實不少，只是我們身處其中的時候往往習以為常了。
舉個例子，比如A和B兩個人都是社會精英，兩人名下都有一大筆資產。突然某一天，兩個人宣佈結婚了，那麼很顯然，一般情況下兩個人的資產會被合併成夫妻共同財產。如果我們把它們兩人的資產都看成是一個集合，那麼結婚其實就代表了這兩個集合進行合併。再舉一個例子，比如在古時候交通不便，河兩岸的村莊往往很少來往。如果某一天河上建了一座橋，連通了河兩岸，如果我們把兩岸的緊密來往的村莊各自看成是一個集合，橋的建成顯然也會讓這兩個集合合併。
上面的例子都是關於集合合併的， 關於集合查找的例子也很多。最經典的就是DNA檢測，比如經常會有一些人號稱自己是某某家族的後代。如果我們想要驗證他們的身份最好的辦法就是去查DNA譜系，我們人有一半的基因來自父親，一半的基因來自母親，這些基因也可以看成是集合。如果某個人號稱是某朝皇室，我們把皇室的基因和他自己家族的基因一匹配，發現並非來自同一個集合，那麼自然這些論調就不告而破了。據說科學家用這種方法考證了中山靖王劉勝並非劉邦的後裔，而是來自某個不知名的南方種群。
並查集正是解決了這兩類集合相關的問題，即集合的合併與查找。
集合的查找
首先我們來看集合的查找，我們還是看上面那個例子，我們怎麼判斷兩個不同的人是否來自同一個家族呢？
這個很簡單，我們只需要查找它們是否有共同的祖先。如果我們基因分析他們兩人的基因來自一個共同的祖先，那麼說明這兩人很有可能來自同一個家族。如果我們把這中間的血緣關係鋪展開來，會得到一棵樹形結構。祖先是樹根，輩分最小的子女是樹葉，和樹一樣，每個節點都只能有一個父節點（把父母看成一個節點），但是可以有多個子節點。
所以我們判斷兩個人是否來源同一個祖先，也就是判斷兩個節點是否在同一棵樹。
由於我們要處理的數據有限，不像基因鏈路那麼長，我們處理這個問題可以很簡單。我們只需要找到這兩個節點所處在的樹的樹根，然後比較它們的樹根是否相等即可。如果相等，說明這兩個節點來自同一棵樹，自然屬於同一個集合，否則則屬於不同的集合。
到這裡，我們不僅知道了應該如何查找兩個節點是否屬於同一個集合，還知道我們應該用樹結構來表示集合。
集合的合併
既然我們明白了我們是通過樹來表示集合，通過查找樹根的方式來判斷兩個節點是否屬於同一個集合，那麼集合合併的操作就變得很簡單了。我們只需要把
兩棵樹合併就行了，如果需要考慮樹深或者是邏輯結構的話，還不太容易，但是我們並不需要那麼多信息，只需要保證集合內的元素正確。我們可以直接把其中一棵樹連到另一顆樹當中。比如我們有A和B兩棵樹需要合併：
我們只需要將B的根節點連到A樹上即可：
這樣原來A樹和B樹上所有的節點都屬於同一個集合，使用我們剛才查找的邏輯得出的結果也是正確的。但是我們分析一下會發現，如果我們這樣合併兩棵樹的話會導致合併之後的樹深變長，這樣會使得我們後續查找的效率變低，因為我們從葉子節點到根節點變得更遠了。所以我們可以直接將B樹的樹根指向A樹的樹根：
代碼實現
對於樹上的每一個節點而言，由於我們查找集合需要查找它們的樹根，而不是葉子。所以對於樹上的每一個節點而言，我們只需要記錄它們的父節點即可。我們可以用一個dict存儲所有節點的父節點，對於根節點而言，我們通常將它的父節點設置成它自己。也就是說當我們找到一個節點的父節點等於它自己的時候，就說明我們已經找到了樹根。
明白了這個邏輯之後，我們用代碼實現就變得非常簡單：
<code>father = {}
def query(x):
if father[x] == x:
return x
return query(father[x])
def union(a, b):
fa, fb = query(a), query(b)
if fa == fb:
return
father[fb] = fa/<code>你看，這段代碼十行都不到，這樣當然是可以work的，但是它還有很大進步的空間。
效率優化
雖然我們已經實現了算法，但是這並不是最優的，我們還可以進行一些優化。首先我們比較容易想到，既然我們每次判斷元素是否在同一個集合是通過樹根來判斷的，並且我們並不在意樹的結構，我們只在意樹根是什麼。既然如此，我們完全可以不用保留樹的結構，讓它變得扁平，讓除了根節點之外的節點都是葉子節點，比如這樣：
這兩個棵樹我們查詢的結果是一樣的，節點數和邊的數量也是一樣的，但不同的是左邊的樹我們查詢樹根最多需要遍歷3次，但是右邊的所有節點都最多隻需要進行一次查詢。如果樹的結構更加複雜，那麼這個優化還會更加明顯。
但問題是我們做樹結構的變動也是需要開銷的，理論上來說每次我們進行合併之後，樹結構都會發生變化。難道我們每次合併之後都需要耗費 O(n) 的時間進行樹的重構嗎？但我們並不能確定查找和合並出現的比例，有可能查找的情況很多，那我們重構樹就是非常划算的，如果查找很少，大部分都是合併操作，那可能我們花了很大的代價進行了樹重構，但是卻沒派上用場。
另外一個問題是，我們重構樹是針對樹上所有節點而言的，我們把所有節點都抬升到了根節點的子節點。但問題是可能並不是所有節點都參與查找的，有可能我們只查找其中幾個節點的情況，那其餘的節點我們也同樣白白計算了。
針對這個問題，有一個非常簡單也非常絕妙的優化——懶惰運算。
懶惰運算我們不是第一次遇見了，之前介紹替罪羊樹的時候就曾經提到過懶惰運算。在替罪羊樹當中，由於我們刪除節點會導致樹結構發生變化，這會帶來大量開銷。所以我們就不刪除節點，而是給它打上一個已經刪除的標記。這樣當我們查找到這個節點的時候，這個節點當中的內容不參與查詢，從而模擬刪除。當打上了刪除標記的節點數量達到一定程度的時候，我們再將它們整體批量刪除。
在並查集當中同樣用到了這樣的懶惰計算的思想，如果我們要進行樹的重構，那麼勢必需要查找根節點。查找根節點需要開銷，那除了重構樹的時候，還有什麼情況下會需要重找根節點呢？很明顯，就是當我們查找兩個節點是否屬於同一個集合的時候。既然如此，我們可以一邊查找一邊重構，將查找這條鏈路上所有的節點全部指向根節點。
我們來舉個例子，假設某一次查找的是下圖當中的F元素，那麼查找完成之後，整棵樹會變成右邊的樣子：
我們用遞歸很容易實現這個邏輯，非常簡單：
<code> def query(x):
if father[x] == x:
return x
father[x] = query(father[x])
return father[x]/<code>
除此之外，我們還有另外一個優化。就是在我們合併兩棵樹的時候，其實我們合併的順序是會影響合併之後的結果的。我們用下圖舉個例子：
從圖中可以看到，同樣是兩棵子樹相加，A+B和B+A的結果是不同的。這兩個結果當然都是正確的，但問題在於它們的深度不同。我們把樹深更小的B加到樹深更大的A上得到的結果樹深是3，但如果反過來，得到的樹深會是4。所以我們會想到可以維護每一棵子樹的樹深，當我們進行合併的時候，永遠把樹深小的加到樹深大的上面，而不是相反。
最後，我們把所有的思路全部整合，寫出完整的代碼，非常簡單，核心邏輯只有40行不到。
<code>class DisjointSet:
def __init__(self, element_num=None):
self._father = {}
self._rank = {}
# 初始化時每個元素單獨成為一個集合
if element_num is not None:
for i in range(element_num):
self.add(i)
def add(self, x):
# 添加新集合
# 如果已經存在則跳過
if x in self._father:
return
self._father[x] = x
self._rank[x] = 0
def _query(self, x):
# 如果father[x] == x，說明x是樹根
if self._father[x] == x:
return x
self._father[x] = self._query(self._father[x])
return self._father[x]
def merge(self, x, y):
if x not in self._father:
self.add(x)
if y not in self._father:
self.add(y)
# 查找到兩個元素的樹根
x = self._query(x)
y = self._query(y)
# 如果相等，說明屬於同一個集合
if x == y:
return
# 否則將樹深小的合併到樹根大的上
if self._rank[x] self._father[x] = y
else:
self._father[y] = x
# 如果樹深相等，合併之後樹深+1
if self._rank[x] == self._rank[y]:
self._rank[x] += 1
# 判斷是否屬於同一個集合
def same(self, x, y):/<code>
總結
如果你仔細思考會發現樹深優化有一點點問題，因為我們在查詢樹根的時候做了樹的重構處理，所以很有可能在此過程當中樹深會發生變化。比如剛好我們查找的是樹深最深的葉子節點，那麼查找之後樹深會減小。但是雖然有這麼一個小問題，但是對我們實際使用的影響不大。一個是因為這種情況發生的概率並不大，另一個是即使發生了也不會帶來很糟糕的後果，單次合併順序不對，至多隻會讓樹上小部分的節點的樹深有常數級別的偏差。
除此之外，還有一些其他的優化方法，比如根據樹的節點數來作為合併的依據。每次將節點少的樹合併進節點數多的樹當中，我個人覺得這個更不靠譜，因為節點越多的樹並不一定樹深越大，很有可能樹深更小。所以總體來說一般我們還是習慣使用樹深作為依據。
並查集這個算法非常經典，它並不難理解，代碼量也很少，效率也高，學習曲線也很平滑，可以說除了使用場景比較窄之外幾乎沒有缺點。畢竟世上沒有完美無缺的算法，這也是算法的魅力所在吧。
希望大家都能有所收穫，原創不易，厚顏求個關注~
閱讀更多 承志的算法課堂 的文章
