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

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

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

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

0 引 言

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

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

1 實例問題

2 Kruskal算法

2.1 算法思想

3 回路判定算法

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

3.1 割邊判定法

3.1.1 算法描述

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

3.1.2 算法分析

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

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

step1 建立數(shù)組記錄每個頂點的度。

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

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

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

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

3.2.1 算法描述

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

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

step2 訪問隊頭頂點，將其被訪問次數(shù)加1；

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

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

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

4 算法性能分析

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

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

4.1.1 割邊判定法

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

4.2 有效性分析

5 結(jié) 語

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

參考文獻(xiàn)

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

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

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

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

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

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