并查集算法及其應用淺析

摘 要：并查集是一種樹型的數據結構，用來處不相交集合的查詢與合并問題。本文介紹了并查集的算法及其思想，針對其某些問題提出改進措施，并探討并查集的應用。

關鍵詞：并查集;應用;算法分析

問題引入

2020年新型冠狀病毒席卷全球。如果一個感染者走進一個群體，并且沒有任何個人防范措施，那么這個群體需要盡快找到并且隔離。那么如何找到與感染者接觸的群體？我們可以用并查集來進行解決。

下面將上述問題提取出數學模型，便于我們進一步分析問題。

首先我們對群體中的每個人進行編號，用N來表示，為了在數組中表示方便，我們將N的取值范圍設置為0～N-1。我們將群體數目用M來進行表示。

接著我們從算法的角度討論程序的輸入與輸出。程序的輸出是，給定一個編號，尋找和這個人接觸的群體。即假設編號為x是我們發現的感染者，輸出與x接觸的人的編號以及所有接觸者的數量。同樣上個例子，我們尋找與編號5接觸的人的編號，即輸出6，7，8，9，數目為4人。

1.并查集算法及其思想

1.1存儲結構

Bernard A. Galler和Michael J. Fischer于1964年提出了并查集的森林表示形式：用一顆多叉樹來表示一個集合，樹中的每個節點都保存著對它父節點的引用，所有的不相交集合即可形成一個森林，并且每個集合的“代表”就是對應的樹的根節點。

可以用雙親表示法，下面以數組存儲結構為例介紹集合的表示方法。數組中每個元素的類型可以表示為如下：

typedef struct{

elementType data;

int parent;

}set

其中elementType 是在頭部定義的數據類型，可以根據需要進行更改。

比如如下集合

可以用結構體數組來進行存儲，存儲方式如下：

注：我們用負數表示根節點，非負數表示表示雙親節點的下標。

1.2算法實現

并查集算法主要涉及三種操作，初始化，查找和合并。其中初始化是將所有數據的parent變量賦值為-1。

查找某個元素屬于哪個集合，以及對兩個集合進行合并。

查找某個元素所在的集合，采用上述存儲結構，代碼如下，我們用根節點表示所在集合。以C語言為例。

int find（set s[]，elementType x）

{

int i;

for（i=0;i

if（i>=maxsize） return -1;

for（;s[i].parent>=0;i=s[i].parent）

return i;

}

void union（set s[]，elementType x1， elementType x2）

{

int root1，root2;

root1=find（s，x1）;

root2=find（s，x2）;

if（root1！=root2）

s[root2].parent=root1;

}

2.并查集改進

2.1數據結構的改進：當數據為int 類型時，我們可以用數組的下標來表示數據。

程序的改進如下：

相應的函數變為如下：

int find（set s[]，elementType x）

{

for（;s[x]>=0;x=s[x]）

return x;

}

union 函數中將最后一行代碼改為如下

s[root2]=root1;

分析：改造后的程序，從空間上減少了對于數據編號的存儲，降低了數據的冗余，從時間看，在find函數中減少了一次for循環，當數據量很大，比如超過10的4次方時，會大大加快程序的速度。但是這種改進僅限于存儲的數據類型也是int類型的時候，具有一定的局限性。

2.2union函數的改進

我們發現union 函數要調用find函數，即首先找到兩個元素的根節點，判斷是否在一個集合內，即判斷根是否相等，如果不同再進行歸并。當數據為n時，union的時間復雜度達到n的平方。所以在進行樹之間的合并時，需要先判斷樹的高度，將矮的樹掛在高的樹上，這樣就不會存在樹隨著合并次數的增多逐漸增高的問題。

那么如何存儲樹的高度呢，我們可以在結構體中再增加一個變量，保存樹的高度，但是這種做法浪費存儲空間?？梢杂么笮肀硎緲涞母叨?。

偽代碼如下：

if（root2高度>root1高度）

s[root1]=root2;

else

{? if（兩者等高） 樹高++;

s[root2]=root1;

}

通過改進時間復雜度降低到logn。這種方法我們稱為按秩歸并。

2.3路徑壓縮

上述算法在一定程度上降低了樹的高度，但是當兩顆樹的高度相同時還是會面臨像上述所述情況的發生。路徑壓縮的思想是先找到某個元素x的根節點，然后把根變成x的父節點，然后返回根，這樣下次再找x時，通過x就能直接找到根，直接降低了根到元素之間的距離。代碼如下：

int find（set s[]，elementType x）

{

if（s[x]<0） return x;

else return s[x]=find（s，s[x]）

}

算法采用了遞歸，將遞歸遍歷中遍歷過的節點都變成根節點的兒子節點，降低了樹的高度，提高了算法的效率。但是這種方法適用于元素數量比較大的情況，當數量集比較小的時候，算法的優勢表現不出。

3并查集相關應用

并查集的思想在解決很多問題上得到了應用，下面簡單舉幾個例子。

3.1 Kruskal算法中求最小生成樹的問題上。的核心思想是在圖中將所有的邊按照從小到大排序，每次選取最小邊并入選出的最小生成樹的集合中去，但是選出的邊不準許存在環路。我們可以用并查集的思想解決，當選出的邊與其他邊在同一個集合中，那么跳過這條邊。

3.2找親戚問題。如果某個家族人員過于龐大，要判斷兩個是否是親戚也很不容易。可以根據目前已知的親戚種族關系判斷給出的兩個人是否有親戚關系。

結語

并查集這種數據結構十分的巧妙，可以有效快速解決有關集合合并、元素歸屬等問題。它是一種工具，應用于解決很多問題。其中在圖的應用中解決點與點的幾何關系，維護圖的關系，使問題迎刃而解。

參考文獻：

[1]王曉東.數據結構（C語言描述）.第3版.北京.電子工業出版社，2019

作者簡介：

姓名：滿冉冉，1991 年2? 月，籍貫：山東滕州，性別 ： 女 ，最高學歷：研究生 ，職稱：助理實驗師 ，職務： 科員，研究方向：計算機應用技術 ， 畢業院校：大連大學。