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

朱伶虎 吳超 張帥杰 陳健

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

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

中圖分類號：TP311? ? ?文獻標識碼：A

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

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

1 模型建立

1.1 問題的描述

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

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

1.2 建立模型

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

為方便研究，現(xiàn)以數組作為基本的數據結構，以數組的下標作為研究的對象。如下圖所示：

2 QF、QU和WQU

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

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

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

3 壓縮路徑算法（CP_WQU）

3.1 基本思想

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

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