1、? 概述

并查集（Disjoint set或者Union-find set）是一種樹型的數據結構，常用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。

2、? 基本操作

并查集是一種非常簡單的數據結構，它主要涉及兩個基本操作，分別為：

A． 合并兩個不相交集合

B． 判斷兩個元素是否屬于同一個集合

（1）?????? 合并兩個不相交集合（Union(x,y)）

合并操作很簡單：先設置一個數組Father[x]，表示x的“父親”的編號。那么，合并兩個不相交集合的方法就是，找到其中一個集合最父親的父親（也就是最久遠的祖先），將另外一個集合的最久遠的祖先的父親指向它。

上圖為兩個不相交集合，b圖為合并后Father(b):=Father(g)

（2）?????? 判斷兩個元素是否屬于同一集合（Find_Set(x)）

本操作可轉換為尋找兩個元素的最久遠祖先是否相同。可以采用遞歸實現。

3、? 優化

（1）?????? Find_Set(x)時，路徑壓縮

尋找祖先時，我們一般采用遞歸查找，但是當元素很多亦或是整棵樹變為一條鏈時，每次Find_Set(x)都是O(n)的復雜度。為了避免這種情況，我們需對路徑進行壓縮，即當我們經過”遞推”找到祖先節點后，”回溯”的時候順便將它的子孫節點都直接指向祖先，這樣以后再次Find_Set(x)時復雜度就變成O(1)了，如下圖所示。可見，路徑壓縮方便了以后的查找。

（2）?????? Union(x,y)時，按秩合并

即合并的時候將元素少的集合合并到元素多的集合中，這樣合并之后樹的高度會相對較小。

4、? 編程實現

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

intfather[MAX];?? /* father[x]表示x的父節點*/ intrank[MAX];???? /*rank[x]表示x的秩*/   voidMake_Set(intx) { father[x] = x; //根據實際情況指定的父節點可變化 rank[x] = 0;?? //根據實際情況初始化秩也有所變化 } /* 查找x元素所在的集合,回溯時壓縮路徑*/ intFind_Set(intx) { if(x != father[x]) { father[x] = Find_Set(father[x]); //這個回溯時的壓縮路徑是精華 } returnfather[x]; } /* 按秩合并x,y所在的集合 下面的那個if else結構不是絕對的，具體根據情況變化 但是，宗旨是不變的即，按秩合并，實時更新秩。 */ voidUnion(intx, inty) { x = Find_Set(x); y = Find_Set(y); if(x == y) return; if(rank[x] > rank[y]) { father[y] = x; } else { if(rank[x] == rank[y]) { rank[y]++; } father[x] = y; } }

5、? 復雜度分析

空間復雜度為O(N)，建立一個集合的時間復雜度為O(1)，N次合并M查找的時間復雜度為O(M Alpha(N))，這里Alpha是Ackerman函數的某個反函數，在很大的范圍內（人類目前觀測到的宇宙范圍估算有10的80次方個原子，這小于前面所說的范圍）這個函數的值可以看成是不大于4的，所以并查集的操作可以看作是線性的。具體復雜度分析過程見參考資料（3）。

6、? 應用

并查集常作為另一種復雜的數據結構或者算法的存儲結構。常見的應用有：求無向圖的連通分量個數，最近公共祖先（LCA），帶限制的作業排序，實現Kruskar算法求最小生成樹等。

7、? 參考資料

（1）?????? 并查集：http://www.nocow.cn/index.php/%E5%B9%B6%E6%9F%A5%E9%9B%86

（2）?????? 博文《并查集詳解》：http://www.cnblogs.com/cherish_yimi/

（3）?????? Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp. 498–524.

————————————————————————————————————-

更多關于數據結構和算法的介紹，請查看：數據結構與算法匯總

————————————————————————————————————-

原創文章，轉載請注明：?轉載自董的博客

本文鏈接地址:?http://dongxicheng.org/structure/union-find-set/

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的数据结构之并查集Union-Find Sets的全部內容，希望文章能夠幫你解決所遇到的問題。

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