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 已完成, 結束

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 cc08310112tw 的頭像
    cc08310112tw

    墨墨喵喵喵

    cc08310112tw 發表在 痞客邦 留言(0) 人氣()