Union-Find 並查集算法詳解
摘要:parent = new int[n]。parent = new int[n]。
預計閱讀時間: 10 分鐘
今天講講 Union-Find 算法,也就是常說的並查集算法,主要是解決圖論中「動態連通性」問題的。名詞很高端,其實特別好理解,等會解釋,另外這個算法的應用都非常有趣。
說起這個 Union-Find,應該算是我的「啓蒙算法」了,因爲《算法4》的開頭就介紹了這款算法,可是把我秀翻了,感覺好精妙啊!後來刷了 LeetCode,並查集相關的算法題目都非常有意思,而且《算法4》給的解法竟然還可以進一步優化,只要加一個微小的修改就可以把時間複雜度降到 O(1)。
廢話不多說,直接上乾貨。先解釋一下什麼叫動態連通性吧。
一、問題介紹
簡單說,動態連通性其實可以抽象成給一幅圖連線。比如下面這幅圖,總共有 10 個節點,他們互不相連,分別用 0~9 標記:
現在我們的 Union-Find 算法主要需要實現這兩個 API:
class UF { /* 將 p 和 q 連接 */ public void union(int p, int q); /* 判斷 p 和 q 是否連通 */ public boolean connected(int p, int q); /* 返回圖中有多少個連通分量 */ public int count(); }
這裏所說的「連通」是一種等價關係,也就是說具有如下三個性質:
1、自反性:節點 p
和 p
是連通的。
2、對稱性:如果節點 p
和 q
連通,那麼 q
和 p
也連通。
3、傳遞性:如果節點 p
和 q
連通, q
和 r
連通,那麼 p
和 r
也連通。
比如說之前那幅圖,0~9 任意兩個 不同 的點都不連通,調用 connected
都會返回 false,連通分量爲 10 個。
如果現在調用 union(0, 1)
,那麼 0 和 1 被連通,連通分量降爲 9 個。
再調用 union(1, 2)
,這時 0,1,2 都被連通,調用 connected(0, 2)
也會返回 true,連通分量變爲 8 個。
這樣,你應該大概明白什麼是動態連通性了,Union-Find 算法的關鍵就在於 union
和 connected
函數的效率。那麼用什麼模型來表示這幅圖的連通狀態呢?用什麼數據結構來實現代碼呢?
二、基本思路
注意我剛纔把「模型」和具體的「數據結構」分開說,這麼做是有原因的。因爲我們使用森林(若干棵樹)來表示圖的動態連通性,用數組來具體實現這個森林。
怎麼用森林來表示連通性呢?我們設定樹的每個節點有一個指針指向其父節點,如果是根節點的話,這個指針指向自己。
比如說剛纔那幅 10 個節點的圖,一開始的時候沒有相互連通,就是這樣:
class UF { // 記錄連通分量 private int count; // 節點 x 的節點是 parent[x] private int[] parent; /* 構造函數,n 爲圖的節點總數 */ public UF(int n) { // 一開始互不連通 this.count = n; // 父節點指針初始指向自己 parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; } /* 其他函數 */ }
如果某兩個節點被連通,則讓其中的(任意)一個節點的根節點接到另一個節點的根節點上:
public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; // 將兩棵樹合併爲一棵 parent[rootP] = rootQ; // parent[rootQ] = rootP 也一樣 count--; // 兩個分量合二爲一 } /* 返回某個節點 x 的根節點 */ private int find(int x) { // 根節點的 parent[x] == x while (parent[x] != x) x = parent[x]; return x; } /* 返回當前的連通分量個數 */ public int count() { return count; }
這樣,如果節點p和q連通的話,它們一定擁有相同的根節點:
public boolean connected(int p, int q) { int rootP = find(p); int rootQ = find(q); return rootP == rootQ; }
至此,Union-Find 算法就基本完成了。是不是很神奇?竟然可以這樣使用數組來模擬出一個森林,如此巧妙的解決這個比較複雜的問題!
那麼這個算法的複雜度是多少呢?我們發現,主要 API connected
和 union
中的複雜度都是 find
函數造成的,所以說它們的複雜度和 find
一樣。
find
主要功能就是從某個節點向上遍歷到樹根,其時間複雜度就是樹的高度。我們可能習慣性地認爲樹的高度就是 logN
,但這並不一定。 logN
的高度只存在於平衡二叉樹,對於一般的樹可能出現極端不平衡的情況,使得「樹」幾乎退化成「鏈表」,樹的高度最壞情況下可能變成 N
。
所以說上面這種解法, find
, union
, connected
的時間複雜度都是 O(N)。 這個複雜度很不理想的,你想圖論解決的都是諸如社交網絡這樣數據規模巨大的問題,對於 union
和 connected
的調用非常頻繁,每次調用需要線性時間完全不可忍受。
問題的關鍵在於,如何想辦法避免樹的不平衡呢?只需要略施小計即可。
三、平衡性優化
我們要知道哪種情況下可能出現不平衡現象,關鍵在於 union
過程:
public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; // 將兩棵樹合併爲一棵 parent[rootP] = rootQ; // parent[rootQ] = rootP 也可以 count--;
我們一開始就是簡單粗暴的把 p
所在的樹接到 q
所在的樹的根節點下面,那麼這裏就可能出現「頭重腳輕」的不平衡狀況,比如下面這種局面:
長此以往,樹可能生長得很不平衡。 我們其實是希望,小一些的樹接到大一些的樹下面,這樣就能避免頭重腳輕,更平衡一些 。 解決方法是額外使用一個 size
數組,記錄每棵樹包含的節點數,我們不妨稱爲「重量」:
class UF { private int count; private int[] parent; // 新增一個數組記錄樹的“重量” private int[] size; public UF(int n) { this.count = n; parent = new int[n]; // 最初每棵樹只有一個節點 // 重量應該初始化 1 size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } /* 其他函數 */ }
比如說 size[3] = 5
表示,以節點 3
爲根的那棵樹,總共有 5
個節點。這樣我們可以修改一下 union
方法:
public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; // 小樹接到大樹下面,較平衡 if (size[rootP] > size[rootQ]) { parent[rootQ] = rootP; size[rootP] += size[rootQ]; } else { parent[rootP] = rootQ; size[rootQ] += size[rootP]; } count--; }
這樣,通過比較樹的重量,就可以保證樹的生長相對平衡,樹的高度大致在 logN
這個數量級,極大提升執行效率。
此時, find
, union
, connected
的時間複雜度都下降爲 O(logN),即便數據規模上億,所需時間也非常少。
四、路徑壓縮
這步優化特別簡單,所以非常巧妙。我們能不能進一步壓縮每棵樹的高度,使樹高始終保持爲常數?
這樣 find
就能以 O(1) 的時間找到某一節點的根節點,相應的, connected
和 union
複雜度都下降爲 O(1)。
要做到這一點,非常簡單,只需要在 find
中加一行代碼:
private int find(int x) { while (parent[x] != x) { // 進行路徑壓縮 parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
這個操作有點匪夷所思,看個 GIF 就明白它的作用了(爲清晰起見,這棵樹比較極端):
可見,調用 find
函數每次向樹根遍歷的同時,順手將樹高縮短了,最終所有樹高都不會超過 3( union
的時候樹高可能達到 3)。
PS:讀者可能會問,這個 GIF 圖的 find
過程完成之後,樹高恰好等於 3 了,但是如果更高的樹,壓縮後高度依然會大於 3 呀?不能這麼想。這個 GIF 的情景是我編出來方便大家理解路徑壓縮的,但是實際中,每次 find
都會進行路徑壓縮,所以樹本來就不可能增長到這麼高,你的這種擔心應該是多餘的。
五、最後總結
我們先來看一下完整代碼:
class UF { // 連通分量個數 private int count; // 存儲一棵樹 private int[] parent; // 記錄樹的“重量” private int[] size; public UF(int n) { this.count = n; parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; // 小樹接到大樹下面,較平衡 if (size[rootP] > size[rootQ]) { parent[rootQ] = rootP; size[rootP] += size[rootQ]; } else { parent[rootP] = rootQ; size[rootQ] += size[rootP]; } count--; } public boolean connected(int p, int q) { int rootP = find(p); int rootQ = find(q); return rootP == rootQ; } private int find(int x) { while (parent[x] != x) { // 進行路徑壓縮 parent[x] = parent[parent[x]]; x = parent[x]; } return x; } }
Union-Find 算法的複雜度可以這樣分析:構造函數初始化數據結構需要 O(N) 的時間和空間複雜度;連通兩個節點 union
、判斷兩個節點的連通性 connected
、計算連通分量 count
所需的時間複雜度均爲 O(1)。
至此,算法就說完了。後續可以考慮談幾道用到該算法的有趣問題,敬請期待。