昨天跟前天我們聚焦在 DFS 和 BFS，了解了關於走訪二維陣列表示的圖的基本遍歷與搜索技巧。
要到更複雜的圖論題目前，我們得先聊聊併查集，Union-Find 的這個算法。
併查集旨在解決在一個集合中，各個點是否同屬一個根，是否同屬一個集合，如他的名字，實現根的查找與不同根的集合的合併。
如果這樣講有點抽象，我們可以舉實際一點的例子：就像黑幫的交際，常常會問你是誰底下的、幫誰做事的(Parent)，來確認是不是同一國的。問著問著，可能就要攀比到最上面的老大是誰，才能確保彼此的老大(Parent)，是不是服務於同一個大老大(Root)底下，這就是併查集中的查。經過一翻火拼，比較小的組織可能被併入，變成共有同一個的老大，這就是併查集中的併。
轉化成圖論的角度，可以想像就是有多個節點，查詢公共根的問題。
注意，在這個算法結構裡，相對不關心直屬父親(Parent)，只關心根(Root)，所以在算法結構的自體優化裡，Parent 是有可能變動的，僅保證再不做 Union 的情況下 Root 不變動。
選擇實現這個算法的資料結構我們使用陣列。
這個陣列的索引是有意義的，索引 i 本身代表節點 i，而 arr[i] 表示他的父節點是誰。
假設 n 表示共有編號 0 到 n-1 的節點，則初始建構會寫成。
public int[] nodes;
public void Init(int n){
nodes = new int[n];
for(var i = 0; i < n; i++){
nodes[i] = i;
}
}
所有節點在初始建構的時候父節點都指向自己，表示自成一派。
再來是查根節點的方式，假設查編號為 n 的節點的根(root)節點為誰，實現如下。
public int Find(int n){
return nodes[n] == n ? n : Find(nodes[n]);
}
根節點的父親就是自己，藉由這個方式，我們可以用遞迴寫成這樣的查找程式碼。
也可以用迴圈來寫。
public int Find(int n){
while(nodes[n] != n){
n = nodes[n];
}
return n;
}
最後一個基本法法是併，假設給予 n1 和 n2，判斷這兩個編號的節點是否在同一個集合裡，如果不在，則把兩個集合合併 ─ 把其中一個人的根的父親指向另一人的根，使得兩個集合擁有公共根。
public void Union(int n1, int n2){
var n1Root = Find(n1);
var n2Root = Find(n2);
if(n1Root == n2Root) return;//同一集合，無須調整
nodes[n2Root] = n1Root;
}
至此，就是查併集的基本建構、查、併三個方法，再來我們討論方法效率優化。
假設今天有兩個集合，分別是 [1,2] 和 [3]。
1 3
/
2
要將兩者合併的時候，我們可以想見有兩種合併方法，就是把其中一個的頭接向另一個。
1 3
/ \ \
2 3 1
\
2
就資料結構查詢效率來說，我們應該可以輕易判斷左邊的效率會比較好，右邊已經拉成了將近直條鏈的樣子。
假設我們要找 2 的根節點，左邊只需一次，右邊則需要兩次。
在這個結構裡，高度術語上不稱作高度，而是秩(Rank)，意思是一樣的，[1,2] 的 Rank 是 2，[3] 的 Rank 是 1。
相較本來，我們額外維護 Rank 這個值，合併時以 Rank 高的為主體來避免結構的偏斜。
這個情況下，我們要改寫的是 Union 這個寫法。
public int[] rank;//額外的陣列維護各個點的 Rank，最後一番合併後，有維護的只有是 root 的點
//基礎可是 0 可是 1，比較上影響不大，是 1 就在建構的時候多一行 rank[i] = 1 即可
public void Union(int n1, int n2){
var n1Root = Find(n1);
var n2Root = Find(n2);
if(n1Root == n2Root) return;
if(rank[n1Root] > rank[n2Root]){
nodes[n2Root] = n1Root;
}
else if(rank[n1Root] < rank[n2Root]){
nodes[n1Root] = n2Root;
}
else{
nodes[n2Root] = n1Root;
rank[n1Root]++;
}
}
要注意的是，當兩個集合的 Rank 一樣時，可以任一個集合的祖先為主，合併另一個集合進來。做完這個操作，要對合併別人進來的、新的根結點的 Rank 做增長，以維護這個集合的正確。
(如下示意，本來 Rank 為 1 的兩個集合，合併後集合的 Rank 為 2)
1 + 2 = 1
/
2
邏輯也可以整理後再壓縮，把最後的 if else 換成下面的寫法：
public void Union(int n1, int n2){
var n1Root = Find(n1);
var n2Root = Find(n2);
if(rank[n1Root] >= rank[n2Root]){
nodes[n2Root] = n1Root;
}
else(rank[n1Root] < rank[n2Root]){
nodes[n1Root] = n2Root;
}
if(rank[n1Root] == rank[n2Root] && n1Root != n2Root){
rank[n1Root]++;
}
}
怕自己搞混就用上面單純的寫法，確認自己邏輯清晰的話也可以採用下面的寫法讓條件式看起來更簡潔。
實際上在一般實踐比較少看到這個優化，為什麼呢？因為下面要討論的這個查找壓縮的優化存在。
查找壓縮，顧名思義，在查找的過程中，把大家的父親層盡量壓平，直接壓到當前的根節點，減輕整個結構的 rank，讓 Find 能夠更有效率。
具體效果大概像這樣。
1
/ \
2 3
/ \
4 5
看起來高度均衡，但以 Find(4) 為例，仍要找兩層。
1
/ / \ \
2 3 4 5
這個結構仍然把所有本來在同一集合的節點維持在同一集合中，且所有點最多只要一次尋找就能夠找到根節點，在這個結構裡我們在意的點都仍有被照顧到(在查併集中只在乎根節點差詢是否正確、確保能維持集合關係，不在乎本來父親是誰)，所以是一個有效的壓縮。
如同這個片段的 Title，實際算法我們會寫在尋找的時候做壓縮，因為尋找的時候剛好會經過這個遍歷過程。
重寫後的尋找如下：
public int Find(int n){
if(nodes[n] == n){
return n;
}
else{
var root = Find(nodes[n]);
nodes[n] = root;
return root;
}
}
這樣就能在找到 root 後，逐層把 root 結果保存下來，成功達到路徑壓縮的效果，讓所有的點都直接與根節點相連。
上面有提到，合併時參考 Rank 會較少用的原因就是，路徑壓縮的優點一般更大，且在執行路徑壓縮的時候，不特別處理的情況下，Rank 會亂掉，無法正確在合併時參考。
當然也可以依狀況去維護 Rank，但這樣寫一般較為費時，通常有顧及路徑壓縮，就能達到大部分省時間的目的。
講了理論和基本資料結構，還是來題題目實際練手會更有實感。
題目給了 n 個點，這些點由 edges 連接著，判斷 source 起點是否和給予的 destination 目標點連在一起。
上面敘述就和查併集的概念直接連在一起了：確認 source 和 destination 是否同屬一個集合。
順序如下：
程式碼如下。
public class Solution {
public class UnionFind{
public int[] nodes;
public UnionFind(int n){
nodes = new int[n];
for(var i = 0; i < n; i++){
nodes[i] = i;
}
}
public int Find(int n){
if(nodes[n] == n){
return n;
}
else{
var root = Find(nodes[n]);
nodes[n] = root;
return root;
}
}
public void Union(int n1, int n2){
var n1Root = Find(n1);
var n2Root = Find(n2);
if(n1Root == n2Root){
return;
}
nodes[n2Root] = n1Root;
}
}
public bool ValidPath(int n, int[][] edges, int source, int destination) {
var uf = new UnionFind(n);
for(var i = 0; i < edges.Length; i++){
uf.Union(edges[i][0], edges[i][1]);
}
var sourceRoot = uf.Find(source);
var destRoot = uf.Find(destination);
return sourceRoot == destRoot;
}
}
這樣大概是 Union Find 算法的基礎與實際練習題目，先了解這個概念，接著才能夠更深入去了解圖中的路徑連通相關問題該如何解決。
iThome鐵人賽
看影片追技術