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

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

問題引入

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

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

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

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

1.并查集算法及其思想

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

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

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

typedef struct{

elementType data;

int parent;

}set

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

比如如下集合

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

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

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

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

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

查找某個(gè)元素所在的集合，采用上述存儲(chǔ)結(jié)構(gòu)，代碼如下，我們用根節(jié)點(diǎn)表示所在集合。以C語(yǔ)言為例。

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í)，我們可以用數(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;

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

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

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

那么如何存儲(chǔ)樹的高度呢，我們可以在結(jié)構(gòu)體中再增加一個(gè)變量，保存樹的高度，但是這種做法浪費(fèi)存儲(chǔ)空間。可以用大小來表示樹的高度。

偽代碼如下：

if（root2高度>root1高度）

s[root1]=root2;

else

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

s[root2]=root1;

}

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

2.3路徑壓縮

上述算法在一定程度上降低了樹的高度，但是當(dāng)兩顆樹的高度相同時(shí)還是會(huì)面臨像上述所述情況的發(fā)生。路徑壓縮的思想是先找到某個(gè)元素x的根節(jié)點(diǎn)，然后把根變成x的父節(jié)點(diǎn)，然后返回根，這樣下次再找x時(shí)，通過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)，降低了樹的高度，提高了算法的效率。但是這種方法適用于元素?cái)?shù)量比較大的情況，當(dāng)數(shù)量集比較小的時(shí)候，算法的優(yōu)勢(shì)表現(xiàn)不出。

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

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

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

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

結(jié)語(yǔ)

并查集這種數(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語(yǔ)言描述）.第3版.北京.電子工業(yè)出版社，2019

作者簡(jiǎn)介：

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