關(guān)于Kruskal算法的環(huán)路判定問(wèn)題研究

摘要： 最小生成樹(shù)（MST）問(wèn)題在很多現(xiàn)實(shí)應(yīng)用中發(fā)揮著重要的作用，Kruskal算法是求最小生成樹(shù)的常用算法之一。由于該算法需要反復(fù)進(jìn)行回路檢測(cè)，故而在實(shí)際應(yīng)用中更適合在圖上直接作業(yè)而不適于直接使用計(jì)算機(jī)進(jìn)行求解。討論了算法的實(shí)現(xiàn)步驟，著重設(shè)計(jì)并分析了相關(guān)回路檢測(cè)算法，證明了他們的正確性。通過(guò)程序?qū)λ惴ǖ膹?fù)雜度進(jìn)行分析，并對(duì)其有效性進(jìn)行了測(cè)試，找出了這些回路檢測(cè)算法的優(yōu)缺點(diǎn)及適用范圍，對(duì)于使用Kruskal算法進(jìn)行計(jì)算機(jī)求解的過(guò)程有一定的指導(dǎo)意義。

關(guān)鍵字： 復(fù)雜度分析； 最小生成樹(shù)； Kruskal算法； 回路檢測(cè)算法

中圖分類(lèi)號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2013）06?0022?03

0 引 言

圖是一種多對(duì)多的復(fù)雜的網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，當(dāng)給圖的各條邊賦予具有一定實(shí)際意義的數(shù)值時(shí)，就成為賦權(quán)圖（也稱為網(wǎng)），賦權(quán)圖是解決一些實(shí)際問(wèn)題的非常有效的工具，而基于連通賦權(quán)圖的最小生成樹(shù)問(wèn)題是其相關(guān)應(yīng)用中非常重要的一個(gè)方面。

求最小生成樹(shù)問(wèn)題，就是要在連通賦權(quán)網(wǎng)絡(luò)中，尋找最小權(quán)數(shù)的支撐樹(shù)。給定網(wǎng)絡(luò)設(shè)為的一個(gè)支撐樹(shù)，令表示的權(quán)和，中權(quán)和最小的支撐樹(shù)稱為的最小生成樹(shù)[1]。

1 實(shí)例問(wèn)題

2 Kruskal算法

2.1 算法思想

3 回路判定算法

對(duì)于回路判定常用兩種算法，本文稱之為割邊判定法和改進(jìn)BFS判定法。

3.1 割邊判定法

3.1.1 算法描述

對(duì)于圖G，查找其度為1的頂點(diǎn)，如果存在則將其相關(guān)邊刪除，并將該頂點(diǎn)及其鄰接點(diǎn)度數(shù)減1，并且繼續(xù)查找度為1的頂點(diǎn)重復(fù)上述操作；如果不存在，則可判斷出是否存在回路。這時(shí)，圖G中邊數(shù)大于等于1，則說(shuō)明圖G存在回路，反之邊數(shù)為0，則說(shuō)明不存在回路

3.1.2 算法分析

任意圖G，如果存在回路，必存在一個(gè)子圖，是一個(gè)環(huán)路。而環(huán)路中所有頂點(diǎn)的度[5]必然大于等于2。由此可推論，如果某頂點(diǎn)度為1，則該頂點(diǎn)必然不在環(huán)路中，那么將其刪除也不會(huì)改變圖中本來(lái)存在的環(huán)路，也不會(huì)影響到回路的判斷。圖2中，v1度為1，將其相關(guān)邊刪除，{v0，v2，v3，v0}的回路依然存在。同理繼續(xù)刪除度為1頂點(diǎn)相關(guān)邊，直到無(wú)度為1頂點(diǎn)為止，該回路均不受影響。而此時(shí)剩下的邊與相關(guān)頂點(diǎn)構(gòu)成了原圖G的環(huán)路子圖（虛線所標(biāo)出部分），而該子圖中的頂點(diǎn)均度數(shù)大于等于2。就說(shuō)明圖G存在環(huán)路子圖，因而判定回路存在。反之，環(huán)路子圖不存在，而判定不存在回路。

3.1.3 算法實(shí)現(xiàn)步驟

step1 建立數(shù)組記錄每個(gè)頂點(diǎn)的度。

step2 在數(shù)組中查找度為1的頂點(diǎn)，如果不存在轉(zhuǎn)到step4，否則執(zhí)行step3。

step3 在圖中查找其鄰接點(diǎn)，將相關(guān)邊刪除，并將該頂點(diǎn)與其鄰接點(diǎn)度數(shù)各減1，并跳轉(zhuǎn)回step2。

step4 查找度數(shù)大于等于2的頂點(diǎn)，如果存在說(shuō)明存在回路，否則不存在回路。

3.2 改進(jìn)BFS判定法

3.2.1 算法描述

假設(shè)訪問(wèn)起點(diǎn)為v1，經(jīng)過(guò)改進(jìn)BFS算法訪問(wèn)若干頂點(diǎn)后訪問(wèn)到vi，直到遍歷結(jié)束，vi也只被訪問(wèn)過(guò)1次。這說(shuō)明v1到vi之間存在惟一路徑，由此可推知經(jīng)訪問(wèn)起點(diǎn)到任意頂點(diǎn)都只存在惟一路徑。又因?yàn)榕卸ㄆ鹗柬旤c(diǎn)的任意性，也就說(shuō)明，任意兩點(diǎn)之間均只存在惟一路徑。故而判定不存在回路。

3.2.3 算法實(shí)現(xiàn)步驟

step2 訪問(wèn)隊(duì)頭頂點(diǎn)，將其被訪問(wèn)次數(shù)加1；

step3 如果該頂點(diǎn)被訪問(wèn)次數(shù)為2則說(shuō)明存在回路，并且算法結(jié)束；

step4 將被訪問(wèn)頂點(diǎn)的前驅(qū)頂點(diǎn)外的所有鄰接點(diǎn)進(jìn)隊(duì)；

step5 如果隊(duì)列不為空，轉(zhuǎn)到step2，否則說(shuō)明不存在回路，并且算法結(jié)束。

4 算法性能分析

圖存儲(chǔ)結(jié)構(gòu)采用鄰接矩陣法，使用JAVA實(shí)現(xiàn)，假定判定對(duì)象圖G頂點(diǎn)數(shù)為n。

4.1時(shí)間復(fù)雜度分析

4.1.1 割邊判定法

4.1.2 改進(jìn)BFS判定法

4.2 有效性分析

5 結(jié) 語(yǔ)

從時(shí)間復(fù)雜度上來(lái)看改進(jìn)BFS判定法時(shí)間復(fù)雜度較小，但是該算法在進(jìn)行判定之前需要判定對(duì)象必須為連通圖，否則就可能出現(xiàn)判定錯(cuò)誤。而割邊判定法雖時(shí)間復(fù)雜度較大，但是對(duì)判定對(duì)象沒(méi)有特殊要求。討論Kruskal算法的推演過(guò)程可知，在最小生成樹(shù)的創(chuàng)建過(guò)程中，新邊加入不一定能構(gòu)成連通圖，所以割邊判定法更適合用于Kruskal算法。

參考文獻(xiàn)

[1] 袁衛(wèi)東.最小生成樹(shù)的算法及其應(yīng)用[J].科學(xué)技術(shù)與工程，2009（15）：51?53.

[2] 黃坤.基于Kruskal算法的最小生成樹(shù)的構(gòu)建[J].電腦知識(shí)與技術(shù)，2010（23）：42?45.

[3] 徐建軍，沙力妮.一種新的最小生成樹(shù)算法[J].電力系統(tǒng)保護(hù)與控制，2011（14）：107?112.

[4] 李春葆.數(shù)據(jù)結(jié)構(gòu)教程[M].2版.北京：清華大學(xué)出版社，2007.

[5] 高淑玲，倫怡.判定連通圖中歐拉通路（或回路）的算法[J].河北建筑工程學(xué)院學(xué)報(bào)，2002（3）：75?76.

[6] 王學(xué)軍.數(shù)據(jù)結(jié)構(gòu)[M].北京：人民郵電出版社，2008.