基于Java語言對動態連通性算法的研究

張帥 方歡 鞠悅

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

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

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

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

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

1問題的提出

1.1問題提出

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

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

1.2動態連通性性質

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

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

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

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

1.3問題的簡單實現

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

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

根據表1，對問題進行簡單的代碼實現：

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

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

2算法的介紹及實現

2.1快速查找（quick-find）

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

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

2.2快速合并（quick-union）

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

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

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