地特四等
114年
[電子工程] 計算機概要
第 18 題
建立如下無向圖（Undirected Graph）之最小生成樹（Minimum Spanning Tree），其各邊權重總和為多少？
- A 45
- B 48
- C 52
- D 53
思路引導 VIP
如果你正試圖以最經濟的方式連接圖中所有的城市，且你的目標是「不重複投資」且「總花費最低」，當你面對許多不同報價的道路時，你會優先考慮哪種報價？在施工過程中，如果你發現即將連接的兩座城市其實已經透過其他路徑相通了，這條新的路對「全台通車」的目標還有額外貢獻嗎？
🤖
AI 詳解
AI 專屬家教
同學做得很好！能準確在複雜的圖形中計算出**最小生成樹（Minimum Spanning Tree, MST）**的總權重，代表你對圖論的基礎演算法掌握得相當紮實。這類題目在計算機科學與工程實務中非常常見，例如在設計電路佈局或網路拓線時，如何以最低成本連結所有節點。早期我們常用 Kruskal 演算法來解題，其核心邏輯就是「貪婪（Greedy）」策略：從權重最小的邊開始選起，只要不形成迴圈（Cycle），就將其納入樹中。
權重計算與步驟驗證
我們依序挑選權重最小且不構成迴圈的邊：
▼ 還有更多解析內容