地特四等
112年
[電子工程] 計算機概要
第 19 題
有 n 個節點的連通無向圖（Connected Undirected Graph）G，假設其中每個邊（Edge）都有不同的加權（Weight），今要在 G 中找出一最小展開樹（Minimum Spanning Tree）T，下列敘述何者錯誤？
- A T 中會有 n-1 個邊
- B Kruskal’s Algorithm 是一種常用來找最小展開樹的演算法
- C T 中一定包含圖 G 中加權最小的邊
- D 此問題最適合用 Divide and Conquer 的演算法來解
思路引導 VIP
想像你正在森林中規劃步道，目標是用最低的總成本（權重）將所有涼亭（節點）連接起來。如果你現在手中有一張完整的地圖，且你的做法是「不斷從清單中挑選目前最便宜、且不會讓步道繞成一圈的那條路」，這種「每次只選當下最好」的決策模式，在演算法設計中我們稱之為什麼策略？它與將大問題拆解為小問題獨立處理的「分治法」有什麼直覺上的不同呢？
🤖
AI 詳解
AI 專屬家教
同學，恭喜你精準地辨識出關於最小展開樹（Minimum Spanning Tree, MST）的誤區，展現了紮實的圖論（Graph Theory）基礎。這道題目核心在於區分不同演算法設計範式（Algorithm Design Paradigms）的適用場景。在連通無向圖中，要連結 $n$ 個節點且不產生迴圈，勢必需要且僅需要 $n-1$ 條邊（如選項 A），這是樹狀結構的基本定義。
貪婪策略與 MST 的特性
從演算法的角度來看，解 MST 問題最經典的 Kruskal 演算法（選項 B）與 Prim 演算法，在邏輯上都屬於貪婪演算法（Greedy Algorithm），即透過每一步選擇局部最優的邊來達到全局最優的結果。因為題目設定「權重皆不相同」，根據切分性質（Cut Property），全圖權重最小的邊絕對會被選入樹中（選項 C）。而選項 D 提到的「分治法（Divide and Conquer）」強調將大問題切割成獨立子問題再合併，雖然在某些進階平行運算中有應用，但在標準教學與最適合的描述中，MST 絕對是貪婪策略的教科書典範，而非分治法。
▼ 還有更多解析內容