本文轉載自csdn另一部落客，其原文點這裡。
public int find(int[] parent, int i) {
if (parent[i] != i) {
parent[i] = find(parent, parent[i]);
}
return parent[i];
}
這個DFS函數可以直接将所經過的所有點的parent設定為根，是以可以忽略原文快結尾處id[i] = id[id[i]]變為爺爺節點這一段。
======分界線 ======
本文主要介紹解決動态連通性一類問題的一種算法，使用到了一種叫做并查集的資料結構，稱為Union-Find。
更多的資訊可以參考Algorithms 一書的Section 1.5，實際上本文也就是基于它的一篇讀後感吧。
原文中更多的是給出一些結論，我嘗試給出一些思路上的過程，即為什麼要使用這個方法，而不是别的什麼方法。我覺得這個可能更加有意義一些，相比于記下一些結論。
關于動态連通性
我們看一張圖來了解一下什麼是動态連通性：
假設我們輸入了一組整數對，即上圖中的(4, 3) (3, 8)等等，每對整數代表這兩個points/sites是連通的。那麼随着資料的不斷輸入，整個圖的連通性也會發生變化，從上圖中可以很清晰的發現這一點。同時，對于已經處于連通狀态的points/sites，直接忽略，比如上圖中的(8, 9)。
動态連通性的應用場景：
- 網絡連接配接判斷：
如果每個pair中的兩個整數分别代表一個網絡節點，那麼該pair就是用來表示這兩個節點是需要連通的。那麼為所有的pairs建立了動态連通圖後，就能夠盡可能少的減少布線的需要，因為已經連通的兩個節點會被直接忽略掉。
- 變量名等同性(類似于指針的概念)：
在程式中，可以聲明多個引用來指向同一對象，這個時候就可以通過為程式中聲明的引用和實際對象建立動态連通圖來判斷哪些引用實際上是指向同一對象。
對問題模組化：
在對問題進行模組化的時候，我們應該盡量想清楚需要解決的問題是什麼。因為模型中選擇的資料結構和算法顯然會根據問題的不同而不同，就動态連通性這個場景而言，我們需要解決的問題可能是：
- 給出兩個節點，判斷它們是否連通，如果連通，不需要給出具體的路徑
- 給出兩個節點，判斷它們是否連通，如果連通，需要給出具體的路徑
就上面兩種問題而言，雖然隻有是否能夠給出具體路徑的差別，但是這個差別導緻了選擇算法的不同，本文主要介紹的是第一種情況，即不需要給出具體路徑的Union-Find算法，而第二種情況可以使用基于DFS的算法。
模組化思路：
最簡單而直覺的假設是，對于連通的所有節點，我們可以認為它們屬于一個組，是以不連通的節點必然就屬于不同的組。随着Pair的輸入，我們需要首先判斷輸入的兩個節點是否連通。如何判斷呢？按照上面的假設，我們可以通過判斷它們屬于的組，然後看看這兩個組是否相同，如果相同，那麼這兩個節點連通，反之不連通。為簡單起見，我們将所有的節點以整數表示，即對N個節點使用0到N-1的整數表示。而在處理輸入的Pair之前，每個節點必然都是孤立的，即他們分屬于不同的組，可以使用數組來表示這一層關系，數組的index是節點的整數表示，而相應的值就是該節點的組号了。該數組可以初始化為：
[java] view plain copy print ?
- for(int i = 0; i < size; i++)
- id[i] = i;
即對于節點i，它的組号也是i。
初始化完畢之後，對該動态連通圖有幾種可能的操作：
- 查詢節點屬于的組
數組對應位置的值即為組号
- 判斷兩個節點是否屬于同一個組
分别得到兩個節點的組号，然後判斷組号是否相等
- 連接配接兩個節點，使之屬于同一個組
分别得到兩個節點的組号，組号相同時操作結束，不同時，将其中的一個節點的組号換成另一個節點的組号
- 擷取組的數目
初始化為節點的數目，然後每次成功連接配接兩個節點之後，遞減1
API
我們可以設計相應的API：
注意其中使用整數來表示節點，如果需要使用其他的資料類型表示節點，比如使用字元串，那麼可以用哈希表來進行映射，即将String映射成這裡需要的Integer類型。
分析以上的API，方法connected和union都依賴于find，connected對兩個參數調用兩次find方法，而union在真正執行union之前也需要判斷是否連通，這又是兩次調用find方法。是以我們需要把find方法的實作設計的盡可能的高效。是以就有了下面的Quick-Find實作。
Quick-Find 算法：
[java] view plain copy print ?
- public class UF
- {
- private int[] id; // access to component id (site indexed)
- private int count; // number of components
- public UF(int N)
- {
- // Initialize component id array.
- count = N;
- id = new int[N];
- for (int i = 0; i < N; i++)
- id[i] = i;
- }
- public int count()
- { return count; }
- public boolean connected(int p, int q)
- { return find(p) == find(q); }
- public int find(int p)
- { return id[p]; }
- public void union(int p, int q)
- {
- // 獲得p和q的組号
- int pID = find(p);
- int qID = find(q);
- // 如果兩個組号相等，直接傳回
- if (pID == qID) return;
- // 周遊一次，改變組号使他們屬于一個組
- for (int i = 0; i < id.length; i++)
- if (id[i] == pID) id[i] = qID;
- count--;
- }
- }
舉個例子，比如輸入的Pair是(5， 9)，那麼首先通過find方法發現它們的組号并不相同，然後在union的時候通過一次周遊，将組号1都改成8。當然，由8改成1也是可以的，保證操作時都使用一種規則就行。
上述代碼的find方法十分高效，因為僅僅需要一次數組讀取操作就能夠找到該節點的組号，但是問題随之而來，對于需要添加新路徑的情況，就涉及到對于組号的修改，因為并不能确定哪些節點的組号需要被修改，是以就必須對整個數組進行周遊，找到需要修改的節點，逐一修改，這一下每次添加新路徑帶來的複雜度就是線性關系了，如果要添加的新路徑的數量是M，節點數量是N，那麼最後的時間複雜度就是MN，顯然是一個平方階的複雜度，對于大規模的資料而言，平方階的算法是存在問題的，這種情況下，每次添加新路徑就是“牽一發而動全身”，想要解決這個問題，關鍵就是要提高union方法的效率，讓它不再需要周遊整個數組。
Quick-Union 算法：
考慮一下，為什麼以上的解法會造成“牽一發而動全身”？因為每個節點所屬的組号都是單獨記錄，各自為政的，沒有将它們以更好的方式組織起來，當涉及到修改的時候，除了逐一通知、修改，别無他法。是以現在的問題就變成了，如何将節點以更好的方式組織起來，組織的方式有很多種，但是最直覺的還是将組号相同的節點組織在一起，想想所學的資料結構，什麼樣子的資料結構能夠将一些節點給組織起來？常見的就是連結清單，圖，樹，什麼的了。但是哪種結構對于查找和修改的效率最高？毫無疑問是樹，是以考慮如何将節點群組的關系以樹的形式表現出來。
如果不改變底層資料結構，即不改變使用數組的表示方法的話。可以采用parent-link的方式将節點組織起來，舉例而言，id[p]的值就是p節點的父節點的序号，如果p是樹根的話，id[p]的值就是p，是以最後經過若幹次查找，一個節點總是能夠找到它的根節點，即滿足id[root] = root的節點也就是組的根節點了，然後就可以使用根節點的序号來表示組号。是以在處理一個pair的時候，将首先找到pair中每一個節點的組号(即它們所在樹的根節點的序号)，如果屬于不同的組的話，就将其中一個根節點的父節點設定為另外一個根節點，相當于将一顆獨立的樹程式設計另一顆獨立的樹的子樹。直覺的過程如下圖所示。但是這個時候又引入了問題。
在實作上，和之前的Quick-Find隻有find和union兩個方法有所不同：
[java] view plain copy print ?
- private int find(int p)
- {
- // 尋找p節點所在組的根節點，根節點具有性質id[root] = root
- while (p != id[p]) p = id[p];
- return p;
- }
- public void union(int p, int q)
- {
- // Give p and q the same root.
- int pRoot = find(p);
- int qRoot = find(q);
- if (pRoot == qRoot)
- return;
- id[pRoot] = qRoot; // 将一顆樹(即一個組)變成另外一課樹(即一個組)的子樹
- count--;
- }
樹這種資料結構容易出現極端情況，因為在建樹的過程中，樹的最終形态嚴重依賴于輸入資料本身的性質，比如資料是否排序，是否随機分布等等。比如在輸入資料是有序的情況下，構造的BST會退化成一個連結清單。在我們這個問題中，也是會出現的極端情況的，如下圖所示。
為了克服這個問題，BST可以演變成為紅黑樹或者AVL樹等等。
然而，在我們考慮的這個應用場景中，每對節點之間是不具備可比性的。是以需要想其它的辦法。在沒有什麼思路的時候，多看看相應的代碼可能會有一些啟發，考慮一下Quick-Union算法中的union方法實作：
[java] view plain copy print ?
- public void union(int p, int q)
- {
- // Give p and q the same root.
- int pRoot = find(p);
- int qRoot = find(q);
- if (pRoot == qRoot)
- return;
- id[pRoot] = qRoot; // 将一顆樹(即一個組)變成另外一課樹(即一個組)的子樹
- count--;
- }
上面 id[pRoot] = qRoot 這行代碼看上去似乎不太對勁。因為這也屬于一種“寫死”，這樣實作是基于一個約定，即 p 所在的樹總是會被作為 q 所在樹的子樹，進而實作兩顆獨立的樹的融合。那麼這樣的約定是不是總是合理的呢？顯然不是，比如 p 所在的樹的規模比 q 所在的樹的規模大的多時， p 和 q 結合之後形成的樹就是十分不和諧的一頭輕一頭重的”畸形樹“了。
是以我們應該考慮樹的大小，然後再來決定到底是調用：
id[pRoot] = qRoot 或者是 id[qRoot] = pRoot
即總是size小的樹作為子樹和size大的樹進行合并。這樣就能夠盡量的保持整棵樹的平衡。
是以現在的問題就變成了：樹的大小該如何确定？
我們回到最初的情形，即每個節點最一開始都是屬于一個獨立的組，通過下面的代碼進行初始化：
[java] view plain copy print ?
- for (int i = 0; i < N; i++)
- id[i] = i; // 每個節點的組号就是該節點的序号
以此類推，在初始情況下，每個組的大小都是1，因為隻含有一個節點，是以我們可以使用額外的一個數組來維護每個組的大小，對該數組的初始化也很直覺：
[java] view plain copy print ?
- for (int i = 0; i < N; i++)
- sz[i] = 1; // 初始情況下，每個組的大小都是1
而在進行合并的時候，會首先判斷待合并的兩棵樹的大小，然後按照上面圖中的思想進行合并，實作代碼：
[java] view plain copy print ?
- public void union(int p, int q)
- {
- int i = find(p);
- int j = find(q);
- if (i == j) return;
- // 将小樹作為大樹的子樹
- if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
- else { id[j] = i; sz[i] += sz[j]; }
- count--;
- }
Quick-Union 和 Weighted Quick-Union 的比較：
可以發現，通過sz數組決定如何對兩棵樹進行合并之後，最後得到的樹的高度大幅度減小了。這是十分有意義的，因為在Quick-Union算法中的任何操作，都不可避免的需要調用find方法，而該方法的執行效率依賴于樹的高度。樹的高度減小了，find方法的效率就增加了，進而也就增加了整個Quick-Union算法的效率。
上圖其實還可以給我們一些啟示，即對于Quick-Union算法而言，節點組織的理想情況應該是一顆十分扁平的樹，所有的孩子節點應該都在height為1的地方，即所有的孩子都直接連接配接到根節點。這樣的組織結構能夠保證find操作的最高效率。
那麼如何構造這種理想結構呢？
在find方法的執行過程中，不是需要進行一個while循環找到根節點嘛？如果儲存所有路過的中間節點到一個數組中，然後在while循環結束之後，将這些中間節點的父節點指向根節點，不就行了麼？但是這個方法也有問題，因為find操作的頻繁性，會造成頻繁生成中間節點數組，相應的配置設定銷毀的時間自然就上升了。那麼有沒有更好的方法呢？還是有的，即将節點的父節點指向該節點的爺爺節點，這一點很巧妙，十分友善且有效，相當于在尋找根節點的同時，對路徑進行了壓縮，使整個樹結構扁平化。相應的實作如下，實際上隻需要添加一行代碼：
[java] view plain copy print ?
- private int find(int p)
- {
- while (p != id[p])
- {
- // 将p節點的父節點設定為它的爺爺節點
- id[p] = id[id[p]];
- p = id[p];
- }
- return p;
- }
至此，動态連通性相關的Union-Find算法基本上就介紹完了，從容易想到的Quick-Find到相對複雜但是更加高效的Quick-Union，然後到對Quick-Union的幾項改進，讓我們的算法的效率不斷的提高。
這幾種算法的時間複雜度如下所示：
| Algorithm | Constructor | Union | Find |
| Quick-Find | N | N | 1 |
| Quick-Union | N | Tree height | Tree height |
| Weighted Quick-Union | N | lgN | lgN |
| Weighted Quick-Union With Path Compression | N | Very near to 1 (amortized) | Very near to 1 (amortized) |
對大規模資料進行處理，使用平方階的算法是不合适的，比如簡單直覺的Quick-Find算法，通過發現問題的更多特點，找到合适的資料結構，然後有針對性的進行改進，得到了Quick-Union算法及其多種改進算法，最終使得算法的複雜度降低到了近乎線性複雜度。
如果需要的功能不僅僅是檢測兩個節點是否連通，還需要在連通時得到具體的路徑，那麼就需要用到别的算法了，比如DFS或者BFS。