申論題

給定圖 ?G

• 頂點集合 ?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)}

克魯斯卡爾演算法的步驟

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

   (?,?,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)

2. 初始化：

   • 最小生成樹（MST）集合：空
   • 使用並查集（Union-Find）來管理頂點集合。

3. 選擇邊並檢查是否形成環：

   • 選擇 (?,?,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 的最小生成樹。