close
突然發現幾乎都是半夜發文XDD
其實這是v姊在上課的時候先提出的那個
Kruskal's Algorithm 是把所有的weight從小到大排序
然後從最小的開始連
(課本p.75頁的圖)
目前
A B C D E
0 0 0 0 0
最小的是50
更新陣列
A B C D E
1 0 0 0 1
接下來是60
更新陣列
A B C D E
1 0 2 2 1
接著70
因為C已經設為2了,所以B也要設為2
A B C D E
1 2 2 2 1
到75的時候
兩點分別是B和D,因為B和D都是相同的數字2,所以可以判斷出75加進去會形成cycle而將75捨棄不加入
再來是80
兩點分別是A和D,A陣列裡是1, D則是1,所以可以判斷不會形成circle,可以加入
接著將 BCD 都改為相同的1 (代表相連,都改成1是因為1比2小,統一合併改成比較小的數字)
A B C D E
1 1 1 1 1
發現陣列裡的數字均相同,代表Spanning Tree 已完成, 結束
全站熱搜