考你個並查集，你竟然摳腳！_小傅哥

作者：小傅哥
部落格：https://bugstack.cn

沉澱、分享、成長，讓自己和他人都能有所收穫！😄

一、前言

並查集的歷史

1964年， Bernard A. Galler 和 Michael J. Fischer 首次描述了不相交的並查集，1975 年，Robert Tarjan 是第一個證明O(ma(n))（逆阿克曼函式）演算法時間複雜度的上限，並且在 1979 年表明這是受限情況的下限。

2007 年，Sylvain Conchon 和 Jean-Christophe Filliâtre 開發並查集資料結構的半持久版本，並使用證明助手 Coq 將其正確性形式化。 “半持久”意味著結構的先前版本被有效地保留，但訪問資料結構的先前版本會使以後的版本無效。它們最快的實現了幾乎與非持久演算法一樣高效的效能且不執行復雜性分析。

二、並查集資料結構

並查集資料結構（也稱為聯合-查詢資料結構或合併-查詢集）基於陣列實現的一種跟蹤元素的資料結構，這些元素被劃分為多個不相交（非重疊）的子集。

它提供了近乎恆定的時間操作（以逆阿克曼函式為界）來新增新集合、合併現有集合以及確定元素是否在同一個集合中。除了推薦演算法、好友關係鏈、族譜等，並查集在 Kruskal 的演算法中扮演著關鍵角色，用於尋找無向邊加權圖的最小生成樹。

並查集的定義乍一看有些抽象，也不知道到底在什麼場景使用。所以小傅哥給大家舉個例子；在以前江湖上有很多門派，各門派見的徒子徒孫碰面難免切磋。為了不讓大家打亂套，都要喊一句：”報上名來“ —— 在下葉問，佛山詠春派，師承陳華順。那麼對於這樣的場景，我們可以使用並查集給各門派成員合併，方便彙總查詢。如圖；

張無忌：既然你不是明教，也不是武當的，我就不客氣了。
趙敏：不客氣你還能咋！我學過詠春！
張無忌：看招！
趙敏：張無忌放開啊，我討厭你！😒

🤔 但各門派徒子徒孫眾多，如果下回遇到趙敏的A丫鬟的Aa丫鬟，沒等Aa報家門找族譜完事，也被摳腳了咋辦？所以基於這樣的情況，要對並查集的各級元素進行優化合並，減少排查路徑。

為了儘可能少的檢索次數到根元素，在01：粗暴合併的基礎上，有了基於數量、排序的合併方式，同時還包括可以壓縮路徑。這樣再索引到根節點的時間複雜度就又降低了。接下來小傅哥就帶著大家看看各個場景的在程式碼中的操作過程。

三、並查集結構實現

並查集的實現非常巧妙，只基於陣列就可以實現出一個樹的效果（基於陣列實現的還有二叉堆也是樹的結構）。

java public class DisjointSet { // 元素 public int[] items; // 數量【可選】 public int[] count; // 排序【可選】 public int[] rank; }

並查集的元素存放在陣列中，通過對陣列元素的下標索引指向其他元素，構成一棵樹。count 數量、rank 排序，是用於對並查集合並元素時的優化處理。

原始碼地址：https://github.com/fuzhengwei/java-algorithms
本章原始碼：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/disjoint_set
動畫演示：https://visualgo.net/zh/ufds?slide=2—— 並查集結構初次理解還是比較困難的，可以結合學習內容的同時做一些動畫演示。

1. 預設合併 - union(1, 8)

```java @Override public int find(int i) { if (i < 0 || i >= items.length) throw new IllegalArgumentException("Index out of range."); return items[i]; }

@Override public void union(int parent, int child) { int parentVal = find(parent); int childVal = find(child); if (parentVal == childVal) return; for (int i = 0; i < items.length; i ++){ // 所有值等於原孩子節點對應值的都替換為新的父節點值 if (items[i] == childVal){ items[i] = parentVal; } } } ```

目標：union(1, 8) 將8的根節點合併到1的根節點 - union 是合併元素的方法，兩個入參意思是把 child 指向的根節點，指向 parent 指向的根節點。後面所有案例中 union 方法屬性欄位意思相同。 - find 找到元素對應的根節點值，之後使用 union 方法對 items 陣列內的元素全部遍歷，把所有值等於 child 的節點，都替換為 parent 節點值。 - 每次合併都for迴圈比較耗時，所以後續做了一些列的優化。

2. 粗暴合併 - union(1, 8)

```java @Override public int find(int i) { if (i < 0 || i >= items.length) throw new IllegalArgumentException("Index out of range."); // 找到元素的根節點，當i == item[i]，就是自己指向自己，這個節點就是根節點 while (i != items[i]) { i = items[i]; } return i; }

目標：union(1, 8) 將8的根節點合併到1的根節點 - find 迴圈找到置頂節點的最終根節點，例如；8 → 6、6 → 6，那麼說明8的根節點是6，因為6自己指向自己了，它就是根節點。 - union 將 8 指向的根節點 6，更換為 1 指向的根節點 0。最終替換完就是 6 → 0，那麼8的根節點有也是0了。 - 這樣雖然減少了每次 for 迴圈更新，但粗暴的合併會對節點的索引帶來一定的複雜度。所以還需要繼續優化。

3. 數量合併 - union(1, 8)

@Override public void union(int parent, int child) { // 父親節點的根節點下標值 int parentRootIdx = find(parent); // 孩子節點的根節點下標值 int childRootIdx = find(child); if (parentRootIdx == childRootIdx) return; if (count[parentRootIdx] >= count[childRootIdx]) { items[childRootIdx] = items[parentRootIdx]; count[parentRootIdx] += count[childRootIdx]; } else { items[parentRootIdx] = items[childRootIdx]; count[childRootIdx] += count[parentRootIdx]; } } ```

目標：union(1, 8) 將8的根節點合併到1的根節點 & 基於節點的 count 值合併 - find 迴圈找到置頂節點的最終根節點，例如；8 → 6、6 → 6，那麼說明8的根節點是6，因為6自己指向自己了，它就是根節點。 - union 在進行元素的根節點合併時，會判斷哪個根下的元素少，用少的元素合併到多的元素下。因為這樣可以減少多的元素因為處於更低位置所帶來的索引耗時。樹越深，子葉節點越多，越耗時。

4. 排序合併 - union(8, 1)

@Override public void union(int parent, int child) { // 父親節點的根節點下標值 int parentRootIdx = find(parent); // 孩子節點的根節點下標值 int childRootIdx = find(child); if (parentRootIdx == childRootIdx) return; if (rank[parentRootIdx] > rank[childRootIdx]) { items[childRootIdx] = items[parentRootIdx]; } else if (rank[parentRootIdx] < rank[childRootIdx]) { items[parentRootIdx] = items[childRootIdx]; } else { items[childRootIdx] = items[parentRootIdx]; rank[parentRootIdx]++; } } ```

目標：union(8, 1) 將1的根節點合併到8的根節點（其實效果和union(1,8)是一樣的，之所以用union(8, 1)主要體現基於 rank 排序後的合併）& 基於節點的 rank 值合併 - find 迴圈找到置頂節點的最終根節點，例如；8 → 6、6 → 6，那麼說明8的根節點是6，因為6自己指向自己了，它就是根節點。 - union 在進行元素的根節點合併時，會判斷哪個根的排序小，用少的元素合併到大的根元素下。因為這樣可以減少樹深大的元素因為處於更低位置所帶來的索引耗時。樹越深，子葉節點越多，越耗時。 - 那麼此時基於 count、rank 都可以進行優化，不過優化過程中 1→0、0→2 還有2個樹高，也可以優化。這就是壓縮路徑的作用

5. 壓縮路徑 - union(8, 1)

```java @Override public int find(int i) { if (i < 0 || i >= items.length) throw new IllegalArgumentException("Index out of range."); while (i != items[i]) { // 路徑壓縮 items[i] = items[items[i]]; i = items[i]; } return i; }

@Override public void union(int parent, int child) { // 父親節點的根節點下標值 int parentRootIdx = find(parent); // 孩子節點的根節點下標值 int childRootIdx = find(child); if (parentRootIdx == childRootIdx) return; if (rank[parentRootIdx] > rank[childRootIdx]) { items[childRootIdx] = items[parentRootIdx]; } else if (rank[parentRootIdx] < rank[childRootIdx]) { items[parentRootIdx] = items[childRootIdx]; } else { items[childRootIdx] = items[parentRootIdx]; rank[parentRootIdx]++; } } ```

目標：union(8, 1) 在rank合併下，壓縮路徑長度。 - 這裡的 union 方法與4. 排序合併相比並沒有變化，變化的地方主要在 find 過程中壓縮路徑。 - find 基於查詢根元素時，對當前元素值對應的父節點值，替換給當前元素。減少一級路徑，做到壓縮路徑的目的。

四、並查集實現測試

單元測試

```java @Test public void test_04() { IDisjointSet disjointSet = new DisjointSet04(9); System.out.println(disjointSet); System.out.println("\n合併元素：\n"); disjointSet.union(0, 1); disjointSet.union(2, 3); disjointSet.union(2, 1); disjointSet.union(6, 4); disjointSet.union(6, 5); disjointSet.union(6, 7); disjointSet.union(6, 8);

System.out.println(disjointSet);
disjointSet.union(8, 1);
System.out.println(disjointSet);

} ```

關於並查集的測試共有6個案例，文中測試舉例測試第4個，基於 Rank 優化合並。

測試結果

```java 座標 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

排序 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

指向 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

合併元素：

座標 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

排序 | 2 | 1 | 3 | 1 | 1 | 1 | 2 | 1 | 1 |

指向 | 2 | 0 | 2 | 2 | 6 | 6 | 6 | 6 | 6 |

座標 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

排序 | 2 | 1 | 3 | 1 | 1 | 1 | 2 | 1 | 1 |

指向 | 2 | 0 | 2 | 2 | 6 | 6 | 2 | 6 | 6 | ```

經過測試對比圖例和控制檯輸出結果可以看到，(4、5、6、7)→6，6→2，1→0，(0、3)→2，這也是最終樹的體現結果。
其他案例原始碼讀者可以測試驗證除錯，這也可以更好的學習掌握。

更多資料結構