-
克魯斯卡爾算法
鎖定
克魯斯卡爾算法是求連通網的最小生成樹的另一種方法。與普里姆算法不同,它的時間複雜度為O(eloge)(e為網中的邊數),所以,適合於求邊稀疏的網的最小生成樹
[1]
。
- 學 科
- 運籌學 [1]
- 目 的
- 用來查找最小生成樹 [1]
- 類似算法
- 普里姆算法 [1]
目錄
克魯斯卡爾算法基本思想
克魯斯卡爾(Kruskal)算法從另一途徑求網的最小生成樹。其基本思想是:假設連通網G=(V,E),令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=(V,{}),概述圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊,若該邊依附的頂點分別在T中不同的連通分量上,則將此邊加入到T中;否則,捨去此邊而選擇下一條代價最小的邊。依此類推,直至T中所有頂點構成一個連通分量為止
[2]
。
克魯斯卡爾算法過程
1.(4,6,30) 2.(2,5,40) 3.(4,7,42) 4.(3,7,45)
5.(1,2,50) 6.(4,5,50) 7.(3,4,52) 8.(1,3,60)
克魯斯卡爾算法包含
克魯斯卡爾算法思想設計克魯斯卡爾算法函數主要包括兩個部分:首先是帶權圖G中e條邊的權值的排序;其次是判斷新選取的邊的兩個頂點是否屬於同一個連通分量。對帶權圖G中e條邊的權值的排序方法可以有很多種,各自的時間複雜度均不相同,對e條邊的權值排序算法時間複雜度較好的算法有快速排序法、堆排序法等,這些排序算法的時間複雜度均可以達到O(elge)。判斷新選取的邊的兩個頂點是否屬於同一個連通分量的問題是一個在最多有n個頂點的生成樹中遍歷尋找新選取的邊的兩個頂點是否存在的問題,此算法的時間複雜度最壞情況下為O(n)
[4]
。
克魯斯卡爾算法複雜度
克魯斯卡爾算法的時間複雜度主要由排序方法決定,而克魯斯卡爾算法的排序方法只與網中邊的條數有關,而與網中頂點的個數無關,當使用時間複雜度為O(elog2e)的排序方法時,克魯斯卡爾算法的時間複雜度即為O(log2e),因此當網的頂點個數較多、而邊的條數較少時,使用克魯斯卡爾算法構造最小生成樹效果較好
[5-6]
。
克魯斯卡爾算法觀察Kruskal算法
初始時,最小生成樹就是網中所有頂點的集合,它們之間沒有任何一條邊連接,即它們自成一個連通分量。而Kruskal算法的執行過程其實就是一個選取網中權值為最小的邊的過程,即將兩個小的連通分量連接為較大的連通分量,直至所有頂點都在一個連通分量中為止。每當選取網中的一條邊時總會出現以下兩種情況之一:
[7]
②該邊所依附的兩個頂點屬於同一個連通分量。如果選取這條邊作為最小生成樹的一條邊,則必將構成環。因為連通分量中任意兩個頂點間都有路徑相通,一旦再加入一條邊,該邊所依附的兩個頂點之間就有了兩條路徑,即構成了環。故屬於這種情況的邊即使其權值小也應該捨棄
[7]
。
- 參考資料
-
- 1. 寧正元主編;張健等編著,數據結構 用C語言描述,中國水利水電出版社,2000.06,第157頁
- 2. 奚小玲,敖廣武主編,數據結構理論與實踐,東北大學出版社,2014.10,第229頁
- 3. 葉茂功,代文徵主編,數據結構項目化教程,國防工業出版社,2013.09,第139頁
- 4. 朱戰立編著,數據結構,西安電子科技大學出版社,2003.05,第186頁
- 5. 劉喜勳編著,數據結構,中國鐵道出版社,2007.04,第181頁
- 6. 朱戰立編著,數據結構-使用C++語言,西安電子科技大學出版社,2001.02,第257頁
- 7. 侯風巍編著,數據結構要點精析 C語言版,北京航空航天大學出版社,2007,第207頁-第208頁