一、給定一個有權重的圖形 G=(V, W)，V 為頂點集合，W 為邊以及該邊上權重的集合。假設 V={A,B,C,D,E,F}， W={{A,B,2},{A,C,6},{B,D,7},{C,D,4},{C,E,5},{D,F,10},{E,F,9}}，請找出 G 的最小生成樹（Minimum Spanning Tree），並詳細說明執行的步驟。（25分）

詳解 (共 2 筆)

詳解提供者：vivian

minimum spanning tree一定要包含Graph中的所有vertex，而且要使得連結所有vertex的edge之weight總和最小

Kruskal's 演算法

1.挑選A-B邊(2)，此時沒有環，加入此邊

2.挑選C-D邊(4)，此時沒有環，加入此邊

3.挑選C-E邊(5)，此時沒有環，加入此邊

4.挑選A-C邊(6)，此時沒有環，加入此邊

5.挑選B-D邊(7)，此時有環的形成，則不加入此邊

6.挑選E-F邊(9)，此時沒有環，加入此邊

7.因為有五條邊了，就不再檢查了，最後的圖則為minimum spanning tree

詳解提供者：hchungw

頂點集合 ?V：{A, B, C, D, E, F}
邊集合 ?W：
{(?,?,2),(?,?,6),(?,?,7),(?,?,4),(?,?,5),(?,?,10),(?,?,9)}{(A,B,2),(A,C,6),(B,D,7),(C,D,4),(C,E,5),(D,F,10),(E,F,9)}

排序邊：按權重從小到大排序邊：

(?,?,2),(?,?,4),(?,?,5),(?,?,6),(?,?,7),(?,?,9),(?,?,10)(A,B,2),(C,D,4),(C,E,5),(A,C,6),(B,D,7),(E,F,9),(D,F,10)
初始化：
- 最小生成樹（MST）集合：空
- 使用並查集（Union-Find）來管理頂點集合。
選擇邊並檢查是否形成環：
- 選擇 (?,?,2)(A,B,2)：加入 MST，不形成環。
- 選擇 (?,?,4)(C,D,4)：加入 MST，不形成環。
- 選擇 (?,?,5)(C,E,5)：加入 MST，不形成環。
- 選擇 (?,?,6)(A,C,6)：加入 MST，不形成環。
- 選擇 (?,?,7)(B,D,7)：加入 MST，不形成環。
- 邊數達到 ∣?∣−1∣V∣−1（5 條），停止。

最小生成樹包括以下邊：

(?,?,2)(A,B,2)
(?,?,4)(C,D,4)
(?,?,5)(C,E,5)
(?,?,6)(A,C,6)
(?,?,7)(B,D,7)

這些邊構成的圖是原圖 ?G 的最小生成樹。