并查集算法及其應(yīng)用淺析

摘 要：并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用來處不相交集合的查詢與合并問題。本文介紹了并查集的算法及其思想，針對其某些問題提出改進(jìn)措施，并探討并查集的應(yīng)用。

關(guān)鍵詞：并查集;應(yīng)用;算法分析

問題引入

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

下面將上述問題提取出數(shù)學(xué)模型，便于我們進(jìn)一步分析問題。

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

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

1.并查集算法及其思想

1.1存儲結(jié)構(gòu)

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

可以用雙親表示法，下面以數(shù)組存儲結(jié)構(gòu)為例介紹集合的表示方法。數(shù)組中每個元素的類型可以表示為如下：

typedef struct{

elementType data;

int parent;

}set

其中elementType 是在頭部定義的數(shù)據(jù)類型，可以根據(jù)需要進(jìn)行更改。

比如如下集合

可以用結(jié)構(gòu)體數(shù)組來進(jìn)行存儲，存儲方式如下：

注：我們用負(fù)數(shù)表示根節(jié)點(diǎn)，非負(fù)數(shù)表示表示雙親節(jié)點(diǎn)的下標(biāo)。

1.2算法實(shí)現(xiàn)

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

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

查找某個元素所在的集合，采用上述存儲結(jié)構(gòu)，代碼如下，我們用根節(jié)點(diǎn)表示所在集合。以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.并查集改進(jìn)

2.1數(shù)據(jù)結(jié)構(gòu)的改進(jìn)：當(dāng)數(shù)據(jù)為int 類型時，我們可以用數(shù)組的下標(biāo)來表示數(shù)據(jù)。

程序的改進(jìn)如下：

相應(yīng)的函數(shù)變?yōu)槿缦拢?/p>

int find（set s[]，elementType x）

{

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

return x;

}

union 函數(shù)中將最后一行代碼改為如下

s[root2]=root1;

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

2.2union函數(shù)的改進(jìn)

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

那么如何存儲樹的高度呢，我們可以在結(jié)構(gòu)體中再增加一個變量，保存樹的高度，但是這種做法浪費(fèi)存儲空間?？梢杂么笮肀硎緲涞母叨取?/p>

偽代碼如下：

if（root2高度>root1高度）

s[root1]=root2;

else

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

s[root2]=root1;

}

通過改進(jìn)時間復(fù)雜度降低到logn。這種方法我們稱為按秩歸并。

2.3路徑壓縮

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

int find（set s[]，elementType x）

{

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

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

}

算法采用了遞歸，將遞歸遍歷中遍歷過的節(jié)點(diǎn)都變成根節(jié)點(diǎn)的兒子節(jié)點(diǎn)，降低了樹的高度，提高了算法的效率。但是這種方法適用于元素數(shù)量比較大的情況，當(dāng)數(shù)量集比較小的時候，算法的優(yōu)勢表現(xiàn)不出。

3并查集相關(guān)應(yīng)用

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

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

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

結(jié)語

并查集這種數(shù)據(jù)結(jié)構(gòu)十分的巧妙，可以有效快速解決有關(guān)集合合并、元素歸屬等問題。它是一種工具，應(yīng)用于解決很多問題。其中在圖的應(yīng)用中解決點(diǎn)與點(diǎn)的幾何關(guān)系，維護(hù)圖的關(guān)系，使問題迎刃而解。

參考文獻(xiàn)：

[1]王曉東.數(shù)據(jù)結(jié)構(gòu)（C語言描述）.第3版.北京.電子工業(yè)出版社，2019

作者簡介：

姓名：滿冉冉，1991 年2? 月，籍貫：山東滕州，性別 ： 女 ，最高學(xué)歷：研究生 ，職稱：助理實(shí)驗(yàn)師 ，職務(wù)： 科員，研究方向：計算機(jī)應(yīng)用技術(shù) ， 畢業(yè)院校：大連大學(xué)。