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

朱伶虎 吳超 張帥杰 陳健

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

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

中圖分類(lèi)號(hào)：TP311? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）26-0164-04

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（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

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

1 模型建立

1.1 問(wèn)題的描述

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

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

1.2 建立模型

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

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

2 QF、QU和WQU

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

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

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

3 壓縮路徑算法（CP_WQU）

3.1 基本思想

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

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