基于Java語(yǔ)言對(duì)動(dòng)態(tài)連通性算法的研究

張帥 方歡 鞠悅

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

關(guān)鍵詞：動(dòng)態(tài)連通性;快速合并;快速查找;加權(quán)快速查找;運(yùn)行效率

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）01-0267-04

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

1問(wèn)題的提出

1.1問(wèn)題提出

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

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

1.2動(dòng)態(tài)連通性性質(zhì)

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

1）自反性：針對(duì)同一個(gè)對(duì)象是相連的，如p與p是相連的;

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

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

1.3問(wèn)題的簡(jiǎn)單實(shí)現(xiàn)

先對(duì)此問(wèn)題進(jìn)行簡(jiǎn)單的實(shí)現(xiàn)，在解決問(wèn)題時(shí)，數(shù)據(jù)結(jié)構(gòu)的選擇往往將會(huì)直接影響到算法的效率，因此，在解決此問(wèn)題時(shí)，可以使用一個(gè)以標(biāo)識(shí)符0到n作為索引的數(shù)組a[]來(lái)解決此問(wèn)題，通過(guò)判斷和改變每個(gè)元素所保存的信息（用整數(shù)表示）實(shí)現(xiàn)連接和判斷連接的操作，若兩個(gè)對(duì)象所保存的a口值相等，則代表它們?cè)谕贿B通分量中，它們是相連的。

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

根據(jù)表1，對(duì)問(wèn)題進(jìn)行簡(jiǎn)單的代碼實(shí)現(xiàn)：

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

在對(duì)問(wèn)題進(jìn)行簡(jiǎn)單實(shí)現(xiàn)之后，下面對(duì)相關(guān)算法做出介紹。

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

2.1快速查找（quick-find）

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

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

2.2快速合并（quick-union）

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

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

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