文章目錄

• 認識并查集
• 并查集解析
• • • 基本思想
    • 如何查看a,b是否在一個集合？
    • a,b合并，究竟是a的祖先合并在b的祖先上，還是b的祖先合并在a上？
    • 其他路徑壓縮？
• 代碼實現
• 結語

認識并查集

對于并查集(不相交集合)，很多人會感到很陌生，沒聽過或者不是特別了解。實際上并查集是一種挺高效的數據結構。實現簡單，只是所有元素統一遵從一個規律所以讓辦事情的效率高效起來。

對于定意義，百科上這么定義的：

并查集，在一些有N個元素的集合應用問題中，我們通常是在開始時讓每個元素構成一個單元素的集合，然后按一定順序將屬于同一組的元素所在的集合合并，其間要反復查找一個元素在哪個集合中。其特點是看似并不復雜，但數據量極大，若用正常的數據結構來描述的話，往往在空間上過大，計算機無法承受；即使在空間上勉強通過，運行的時間復雜度也極高，根本就不可能在比賽規定的運行時間（1～3秒）內計算出試題需要的結果，只能用并查集來描述。

并查集是一種樹型的數據結構，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。常常在使用中以森林來表示。

并查集解析

基本思想

• 初始化，一個森林每個都為獨立。通常用數組表示，每個值初始為-1。各自為根
  
• join(a,b) 操作。a,b兩個集合合并。注意這里的a，并不是a,b合并，而是a,b的集合合并。這就派生了一些情況：
• a，b如果是獨立的(沒有和其他合并)，那么直接a指向b(或者b指向a)，即data[a]=b;同時為了表示這個集合有多少個，原本-1的b再次-1.即data[b]=-2.表示以b為父親的節點有|-2|個。
  
  
• a,b如果有集合(可能有父親，可能自己是根)，那么我們當然不能直接操作a,b(因為a,b可能已經指向別人了.)那么我們只能操作a,b的祖先。因為a,b的祖先是沒有指向的(即數據為負值表示大小)。那么他們首先一個負值要加到另外一個上面去。另外這個數值要變成指向的那個表示聯系。
  

對于上述你可能會有疑問：

如何查看a,b是否在一個集合？

• 查看是否在一個集合，只需要查看節點根祖先的結果是否相同即可。因為只有根的數值是負的，而其他都是正數表示指向的元素。所以只需要一直尋找直到不為正數進行比較即可！

a,b合并，究竟是a的祖先合并在b的祖先上，還是b的祖先合并在a上？

• 這里會遇到兩種情況，這個選擇也是非常重要的。你要弄明白一點：樹的高度+1的化那么整個元素查詢的效率都會降低！

所以我們通常是：小數指向大樹(或者低樹指向高樹)，這個使得查詢效率能夠增加！

當然，在高度和數量的選擇上，還需要你自己選擇和考慮。

其他路徑壓縮？

每次查詢，自下向上。當我們調用遞歸的時候，可以順便壓縮路徑，因為我們查找一個元素其實只需要直到它的祖先，所以當他距離祖先近那么下次查詢就很快。并且壓縮路徑的代價并不大！

代碼實現

并查集實現起來較為簡單，直接貼代碼！

package 并查集不想交集合;import java.util.Scanner; public class DisjointSet {static int tree[]=new int[100000];//假設有500個值public DisjointSet() {set(this.tree);}public DisjointSet(int tree[]) {this.tree=tree;set(this.tree);}public void set(int a[])//初始化所有都是-1 有兩個好處，這樣他們指向-1說明是自己，第二，-1代表當前森林有-（-1）個{int l=a.length;for(int i=0;i<l;i++){a[i]=-1;}}public int search(int a)//返回頭節點的數值{if(tree[a]>0)//說明是子節點{return tree[a]=search(tree[a]);//路徑壓縮}elsereturn a;}public int value(int a)//返回a所在樹的大小（個數）{if(tree[a]>0){return value(tree[a]);}elsereturn -tree[a];}public void union(int a,int b)//表示 a，b所在的樹合并{int a1=search(a);//a根int b1=search(b);//b根if(a1==b1) {System.out.println(a+"和"+b+"已經在一棵樹上");}else {if(tree[a1]<tree[b1])//這個是負數，為了簡單減少計算，不在調用value函數{tree[a1]+=tree[b1];//個數相加 注意是負數相加tree[b1]=a1; //b樹成為a的子樹，直接指向a；}else{tree[b1]+=tree[a1];//個數相加 注意是負數相加tree[a1]=b1; //b樹成為a的子樹，直接指向a；}}}public static void main(String[] args){ DisjointSet d=new DisjointSet();d.union(1,2);d.union(3,4);d.union(5,6);d.union(1,6);d.union(22,24);d.union(3,26);d.union(36,24);System.out.println(d.search(6)); //頭System.out.println(d.value(6)); //大小System.out.println(d.search(22)); //頭System.out.println(d.value(22)); //大小} }

結語

• 并查集屬于簡單但是很高效率的數據結構。在集合中經常會遇到。如果不采用并查集而傳統暴力效率太低，而不被采納。
• 另外，并查集還廣泛用于迷宮游戲中，下面有機會可以介紹用并查集實現一個走迷宮小游戲。大家歡迎關注！
• 最后，歡迎大家關注筆者公眾號，一起學習、交流！筆者學習資源也放置公眾號和大家一起分享！
  

總結

以上是生活随笔為你收集整理的数据结构与算法——并查集(不相交集合)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。