概念

其實並查集顧名思義就是有“合併集合”和“查找集合中的元素”兩種操作的關於數據結構的一種算法。

用途

1. 維護無向圖的連通性。支持判斷兩個點是否在同一連通塊內。
2. 判斷增加一條邊是否會產生環：用在求解最小生成樹的Kruskal算法裡。

操作

並查集主要就三個操作：初始化、合併、查找

初始化

一般來說，並查集的初始化用數組即可，例如數組Tree[i]，i表示某節點，tree[i]表示當前節點的根節點

查找函數

這裡的查找和java集合類List中的查找函數get()並不一樣，他的作用是查找該節點的根節點，如果集合的parent等於集合的編號（即還沒有被合併或者沒有同類），那麼自然返回自身編號。如果不同那麼就可以調用遞歸函數。

代碼如下

 // 並查集查找根節點
 static int findRoot(int x, int[] arr) {
 // 如果集合i的父親是自己，說明自己就是源頭，返回自己的標號
 if (arr[x] == -1)
 return x;
 else // 否則查找集合i的父親的源頭
 return findRoot(arr[x], arr);
 }

若需要在查找過程中添加路徑壓縮的優化，我們修改上面這個函數為：

 // 並查集查找根節點（優化算法,本質是將路徑壓縮了）
 static int findRootUseful(int x, int[] arr) {
 int res = 0;
 if (arr[x] == -1)
 return x;
 else {
 res = findRoot(arr[x], arr);
 arr[x] = res; // 將當前結點的雙親結點設置為查找返回的根結點編號
 return res;
 }
 }

合併

上面的圖片就是關於合併的解法，至於怎麼合併就是要看題目的要求了，詳見代碼示例中的註釋

 //set1表示x所在的集合，set2表示y所在的集合
 // 合併兩個集合,至於按照什麼原則合併就要按照題目意思了，在這裡我定義了兩個變量，用以比較set1和set2的某種屬性之間的差異
 //如果rankX>rankY,就需要把y的集合合併到x的根節點下，也就是set2[y]=x，否則就是將x的集合放到y的根節點下，即set1[x]=y
 static int rankX = 0;
 static int rankY = 1;
 static void union(int x, int y, int[] set1, int[] set2) {
 x = findRootUseful(x, set1);
 y = findRootUseful(y, set2);
 if (x == y)
 return;
 else if (rankX > rankY) {
 set2[y] = x;
 } else {
 if (rankX == rankY)
 rankY++;
 set1[x] = y;
 }
 }

閱讀更多 僱個城管打天下y 的文章

關鍵字: 數據結構 技術 查集