關(guān)于動態(tài)連通性算法的研究

朱伶虎 吳超 張帥杰 陳健

摘要：在生活中關(guān)于動態(tài)連通性的案例比比皆是，尤其在油田井間、網(wǎng)絡(luò)節(jié)點等方面應(yīng)用較為豐富。在此將針對動態(tài)連通性問題進(jìn)行對其常用的三種算法進(jìn)行探究，完成其三種算法的實現(xiàn)以及測試，而后通過算法的改進(jìn)，選擇出其中運行效率最高的解決動態(tài)連通性問題的算法。

關(guān)鍵詞：動態(tài)連通性;算法;運行效率

中圖分類號：TP311? ? ?文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2021）26-0164-04

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

Research on Dynamic Connectivity Algorithm

ZHU Ling-hu， WU Chao*， ZHANG Shuai-jie， CHEN Jian

（Liupanshui Normal University， Liupanshui 553004， China）

Abstract： In our life， there are many cases about dynamic connectivity， especially in the fields of well to well and network nodes. In this paper， we will explore the three commonly used algorithms for the dynamic connectivity problem， complete the implementation and testing of the three algorithms， and then select the most efficient algorithm to solve the dynamic connectivity problem through the improvement of the algorithm.

Key words： dynamic connectivity; algorithm; operation efficiency

動態(tài)連通性是圖論中的一種用于判斷兩點之間是否相連的數(shù)據(jù)結(jié)構(gòu) [1]。在生產(chǎn)生活中也有比較廣泛的應(yīng)用，如在計算機(jī)網(wǎng)絡(luò)部署中、油田井間、電路芯片的晶體管、照片的像素、數(shù)學(xué)集合中的元素等方面。但常見的動態(tài)連通性算法已經(jīng)跟不上現(xiàn)代社會的發(fā)展速度。本文主要在動態(tài)連通性三種常見算法，quick_find算法（下文用QF表示）、quick_union算法（下文用QU表示）和加權(quán)quick_union算法（下文用WQU表示）的基礎(chǔ)上進(jìn)行研究。從連接路徑的角度出發(fā)，采取壓縮路徑或者減半策略對動態(tài)連通性算法進(jìn)行優(yōu)化，比較其與三種常見算法的效率以及其自身所能達(dá)到的運算數(shù)量級。

1 模型建立

1.1 問題的描述

動態(tài)連通性問題的輸入是一列整數(shù)對，其中每個整數(shù)都表示一個某種類型的對象（例如網(wǎng)絡(luò)中的一臺電腦或者朋友關(guān)系中的一個人），一對整數(shù)R1，R2被理解為相連的，我們假設(shè)“相連”是一種等價關(guān)系，即具備自反性，對稱性，傳遞性三種特性。

動態(tài)連通性問題就是當(dāng)讀取任意一對整數(shù)對時，若用已知關(guān)系可以判斷該對整數(shù)相連，則忽略該對整數(shù)，否則將該對整數(shù)相連，然后打印輸出此整數(shù)對，當(dāng)所有整數(shù)對讀取完畢后，輸出連通分量的數(shù)量。

1.2 建立模型

根據(jù)問題描述，假設(shè)用0—N-1個整數(shù)表示N個對象，現(xiàn)假設(shè)初始狀態(tài)時每個單獨的對象都與本身相連。若對象R1與R2不相連則將他們劃分到一個集合中，若相連則忽略。

為方便研究，現(xiàn)以數(shù)組作為基本的數(shù)據(jù)結(jié)構(gòu)，以數(shù)組的下標(biāo)作為研究的對象。如下圖所示：

2 QF、QU和WQU

QF算法是以數(shù)組ID為基本的數(shù)據(jù)結(jié)構(gòu)，以數(shù)組的下標(biāo)作為研究對象。初始狀態(tài)時所有對象都是相互獨立的。若讀入整數(shù)R1與R2，則比較ID[R1]與ID[R2]是否相同，相同則忽略，不同則將ID[R2]與ID[R2]相同的數(shù)組內(nèi)容改為ID[R1]。在最壞的情況下，QF算法的時間復(fù)雜度時O（N2）。

QU算法同樣是以數(shù)組ID為基本的數(shù)據(jù)結(jié)構(gòu)，以數(shù)組的下標(biāo)作為研究對象。但在對象所構(gòu)造的數(shù)據(jù)結(jié)構(gòu)上是以樹型結(jié)構(gòu)為基礎(chǔ)。每個對象R都是以自己為根節(jié)點的一棵樹，即數(shù)組ID中的內(nèi)容就是對象R本身。當(dāng)讀入整數(shù)R1與R2，若屬于同一棵樹就忽略，若不同則找到R1與R2所在樹的根節(jié)點，將R2所在的樹的根節(jié)點連接到R1所在的樹的根節(jié)點上，完成對象R1與R2的相連。在最壞的情況下，QU算法的時間復(fù)雜度是O（N）～O（N2）。QU算法在整體的效率上要高于QF算法，因為主要影響其時間復(fù)雜度的是樹的高度。

WQU是在QU算法上的進(jìn)一步改進(jìn)，因為影響QU算法的主要問題是樹的高度，而樹的高度的增加是因為在兩棵樹連接時，會出現(xiàn)三種情況，小樹連在大樹上，兩顆相同的樹連接，大樹連在小樹上。后兩種情況會導(dǎo)致樹的高度增加，但兩棵樹相同時，樹的高度只增加1，而大樹連在小樹上，會使得原來小樹的高度大幅度增加，致使QU算法的時間復(fù)雜度增加。WQU是使用一個數(shù)組RS[]記錄樹的大小作為權(quán)值，當(dāng)兩棵樹連接時，將權(quán)值小的樹連接到權(quán)值大的樹上。在最壞的情況下，WQU的時間復(fù)雜度是O（lgN）。相對前兩種算法有了進(jìn)一步的提高。

3 壓縮路徑算法（CP_WQU）

3.1 基本思想

WQU是記錄分量所構(gòu)成樹的大小作為該分量的權(quán)值，然后將權(quán)值小的樹掛在權(quán)值大的樹的根上完成分量的合并，其算法的復(fù)雜度在最壞的情況下是lgN。在加權(quán)QU的基礎(chǔ)上還可以進(jìn)行路徑的壓縮以進(jìn)一步提高算法的效率。

基本思想是當(dāng)?shù)谝淮伪闅v存儲分量的數(shù)組時，將各個分量都指向其根節(jié)點。那么在下一次輸入整數(shù)對R1，R2時，在查找其根節(jié)點的時間復(fù)雜度就是常數(shù)級。缺點是在第一次遍歷數(shù)組時，其時間復(fù)雜度是原來WQU的2倍，但對于之后的算法的效率提高是有顯著作用的。