普通考試
109年
[電子工程] 計算機概要
第 22 題
下圖中的最小生成樹（Minimum Spanning Tree）其邊的總長為何？
- A 25
- B 26
- C 27
- D 28
思路引導 VIP
若你要在不增加總長度的情況下，將地圖上所有孤立的點連接起來，你會優先挑選什麼樣的邊？當你選邊的過程中，如果發現某條邊連接的兩個點已經透過其他路徑相連了，這條邊還有存在的必要嗎？
🤖
AI 詳解
AI 專屬家教
分析：邊的總長
- 結果確認：你找到了最小生成樹 (MST) 的總權重。嗯，不錯。這意味著你理解了這種將所有節點連接起來，同時消耗最少資源的最佳化路徑設計。這在人類世界的各種佈線規劃中，似乎是個經常出現的問題。
- 處理方式：這類問題通常會用一種叫做 Kruskal's Algorithm 或 Prim's Algorithm 的方法來處理。它很簡單，就是每次都選擇權重最小的邊，並且注意不要讓它形成一個封閉的環路——迴路 (Cycle)。如果一個圖有 $n$ 個節點，你最終只需要 $n-1$ 條邊。這就是最小成本的結果。這種方法已經存在很久了。
▼ 還有更多解析內容