阿摩線上測驗
50. 給定下列的圖形 (graph)，若使用Kruskal演算法求最小生成樹，則最小生成樹的總權重值 (total weight) 為何？
(A) 15
(B) 17
(C) 19
(D) 21
答案：登入後查看
統計： A(18), B(159), C(20), D(15), E(0) #2388725
統計： A(18), B(159), C(20), D(15), E(0) #2388725
詳解 (共 2 筆)
RenShiang Jeng
#5396676
Kruskal演算法
思路
步驟如下：
1.以每條邊的權重排序，排非降序。
2.每次挑選一個權重最小的邊，檢查將其加入到最小生成樹時，是否會形成環（一顆樹是沒有環的啊）
3.重複步驟2直到最小生成樹中有V-1條邊。
在步驟2中，我們使用Union-Find algorithm來檢測加入邊是否會形成環。
顯而易見，Kruskal演算法是一種貪心演算法
依本題依序尋找
1(A-B)
2(A-D)
3(B-E)
4(D-E)不成立 會形成ＡＢＥＤ環
尋找下一個數字5(B-C)
6(B-F)
到此已可連結所有的節點，將剛剛成立的邊相加．
1+2+3+5+6=17 為本題答案
2
0
