基于Java語言對動態(tài)連通性算法的研究

張帥 方歡 鞠悅

摘要：動態(tài)連通性是圖論中的一種用于表示兩點之間是否相連的數(shù)據(jù)結構，它可以準確地反映出圖中個點之間的連接信息。動態(tài)連通性的應用廣泛，為尋找出一種能夠有效解決動態(tài)連通性問題的方法，基于java語言對三種動態(tài)連通性算法進行實現(xiàn)和測試，通過對結果的分析，判斷每種算法的運行時間及效率，選擇出最為有效的解決動態(tài)連通性問題的算法。

關鍵詞：動態(tài)連通性;快速合并;快速查找;加權快速查找;運行效率

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

文章編號：1009-3044（2020）01-0267-04

動態(tài)連通性是一種在計算機圖論中的一種數(shù)據(jù)結構，它可以有效地反映出圖結構中對象與對象相連接的組信息，包括在圖中各個點是否相互連接、連接之后會組成多少個信息組。動態(tài)連通性在實際生活中的應用也很多，如油田井間、網絡節(jié)點、路勁優(yōu)化等方面都有著廣泛的應用。本文針對動態(tài)連通性問題進行算法實踐和研究，利用java語言編程對圖節(jié)點快速查找、快速合并以及加權快速合并算法的實現(xiàn)和測試，并總結出三種算法的運行特點以及其中效率最高的解決動態(tài)連通性問題的算法。

1問題的提出

1.1問題提出

先來詳細地說明一下所要求解的問題，假設共有N個對象，這些對象是可以相互連通的，使用0到n的整數(shù)對其進行標記，現(xiàn)在假設程序擁有兩個操作，一個操作是用來連接兩個對象，通過參數(shù)將兩個對象p和q傳入該命令，該命令會對其進行連接操作;另一個操作是對兩個對象連通性的查詢，即查詢p和q之間是否存在連通的路徑，當然，只需要判斷這條路徑是否存在，并不需要找此路徑。

例如圖1所示，假設已經執(zhí)行過相關的連接操作rF文簡稱union），連接了4和8，連接了2和3，連接了3和7等等，接下來可以對圖1進行連通性查詢操作（下文簡稱connected），程序執(zhí)行connected（O，7）操作，觀察圖1，顯然0與7是不具有連通性的，程序執(zhí)行connected（1，9）操作，顯然1與9是連通的。在此也可以進行大量的union操作，女Iunion（3，1），使得圖中的連通分量不斷的減小，最終使得圖1中的每個對象之間都具有連通性，而所要處理的問題是如何在較短的時間內執(zhí)行大量的合并操作和連通查詢操作。

1.2動態(tài)連通性性質

對問題性質的分析，可以更好地實現(xiàn)和改進算法，在動態(tài)連通性問題中，根據(jù)離散數(shù)學，假設兩個對象之間的“相連”是一種等價關系，這也就意味著動態(tài)連通性會具有三個性質：

1）自反性：針對同一個對象是相連的，如p與p是相連的;

2）對稱性：兩個對象相互連接是雙向的，如：p與q是相連的，那么q與p也是相連的;

3）傳遞性：對象與對象的連接是傳遞的，如：p與q是相互連接的，q與r是相互連接的，那么p與r也是相互連接的。結合對問題性質的分析，對所提出的問題進行簡單的實現(xiàn)。

1.3問題的簡單實現(xiàn)

先對此問題進行簡單的實現(xiàn)，在解決問題時，數(shù)據(jù)結構的選擇往往將會直接影響到算法的效率，因此，在解決此問題時，可以使用一個以標識符0到n作為索引的數(shù)組a[]來解決此問題，通過判斷和改變每個元素所保存的信息（用整數(shù)表示）實現(xiàn)連接和判斷連接的操作，若兩個對象所保存的a口值相等，則代表它們在同一連通分量中，它們是相連的。

在實現(xiàn)問題之前，首先需要了解所要實現(xiàn)的操作有哪些，見表1。

根據(jù)表1，對問題進行簡單的代碼實現(xiàn)：

首先讀取一個正整數(shù)N來表示所要研究的對象個數(shù)，利用DC的構造函數(shù)來初始化a口數(shù)組，判斷p和q是否已經連通，若不連通則執(zhí)行連通操作。

在對問題進行簡單實現(xiàn)之后，下面對相關算法做出介紹。

2算法的介紹及實現(xiàn)

2.1快速查找（quick-find）

第一個算法為快速查找算法，通過對問題的分析，最終選擇了數(shù)組作為本次求解問題的數(shù)據(jù)結構，而數(shù)組中的每一項所記錄的為此元素的相連信息，因此當利用java語言實現(xiàn)con-nected（p，q）操作時，只需要判斷兩個對象p和q所記錄的數(shù)值是否相同來判斷他們是否相連，在實現(xiàn)union（p，q）操作時，需要將p節(jié)點所記錄的數(shù)值保存，之后將q所記錄的數(shù)值賦值給p，并利用循環(huán)，將與p所在的同一連通分量的所有對象的a口值全部更改為q所記錄的a口值，來實現(xiàn)合并操作。

結合圖1和圖2，未實現(xiàn)union（3，1）操作時，圖中總共有4個連通分量，分別為{0}，{4，8}，{2，3，7}和{1，6，5，9}，根據(jù)圖2所示，在同一個連通分量中的對象所記錄的a口值是相同的。在執(zhí)行完union（3，1）操作，對象3所記錄的a口值變?yōu)榱?，并且與對象3所在同一連通分量的所有對象的a口值均變?yōu)?，連通分量減少了1，對象3和1實現(xiàn)了連接，代碼實現(xiàn)如下：

2.2快速合并（quick-union）

再利用java語言實現(xiàn)快速合并算法時，將圖中的每一個連通分量以樹的方式表示，在數(shù)組中將每一個元素所記錄的a[]值與父節(jié)點相聯(lián)系，在執(zhí)行union（p，q）操作時，首先，找到p和q節(jié)點的根節(jié)點，之后將p節(jié)點的根節(jié)點的a口記錄值設置為q節(jié)點的根節(jié)點，通過對兩個根節(jié)點相連來實現(xiàn)連通分量的合并。

執(zhí)行union（3，1），首先找到1節(jié)點的根節(jié)點為1，然后找到3節(jié)點的根節(jié)點為2，在圖中將2節(jié)點和1節(jié)點相連，則實現(xiàn)了將3節(jié)點與1節(jié)點的連接操作，使得兩結點在同一連通分量中，而在數(shù)組中只需要將2節(jié)點的a口記錄值設置成為1節(jié)點，便可實現(xiàn)union操作，而connected操作，只需要判斷兩個節(jié)點的根節(jié)點是否相同便可，代碼實現(xiàn)如下：

通過代碼可以看出快速合并算法有一個較大的缺點為快速合并算法依賴于輸入整數(shù)對的隨機性，當操作數(shù)量過大時，快速合并算發(fā)所產生的樹的高度會逐漸增高，最終導致回溯樹尋找根節(jié)點的時間增多，降低算法的運行效率。