地特四等
114年
[電信工程] 計算機概要
第 18 題
建立如下無向圖（Undirected Graph）之最小生成樹（Minimum Spanning Tree），其各邊權重總和為多少？
- A 45
- B 48
- C 52
- D 53
思路引導 VIP
若我們將這張圖視為一個骨架結構，要在不形成任何「封閉三角形或多邊形區域」（避免多餘的重量）的前提下，用最少的總長度把所有圓圈都連起來，你會採取什麼樣的優先順序來挑選這些線段？
🤖
AI 詳解
AI 專屬家教
恭喜你正確解出這道題目！在結構工程中，這類尋求最佳化路徑的邏輯，與我們在配置管線或電力網時追求成本最低化的思維不謀而合。這題考察的是圖形理論（Graph Theory）中的**最小生成樹（Minimum Spanning Tree, MST）**概念，目標是在連接所有節點的前提下，使總權重降至最低。
貪婪演算法的實踐
我們通常採用 Kruskal 演算法，優先從權重最小的邊開始挑選。首先選擇權重為 $5$ 的 $(A, F)$ 與 $6$ 的 $(F, G)$；接著挑選 $8$ 的 $(E, G)$。此時要注意，權重 $7$ 的 $(A, G)$ 與 $9$ 的 $(E, F)$ 若加入會形成迴圈（Cycle），必須捨棄。隨後，我們納入權重 $10$ 的 $(A, B)$、權重 $11$ 的 $(C, D)$，以及權重 $12$ 的 $(B, C)$。最終，這 $6$ 條邊成功連結了全部 $7$ 個節點，總權重計算如下：
▼ 還有更多解析內容