有n 個節點的連通無向圖（Connected Undirected Graph）G，假設其中每個邊（Edge）都有不同的加權（Weight），今要在G 中找出一…

題目

有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 的演算法來解

官方答案

• 答案：D. 此問題最適合用Divide and Conquer 的演算法來解

解析

最小展開樹是貪婪法（Greedy）的典型應用：Kruskal 演算法依權重由小到大逐邊加入且避免成環，Prim 演算法則從任一節點逐步擴張，兩者都不是分而治之，故 D 錯誤。A 正確，n 個節點的生成樹恰有 n−1 條邊。B 正確，Kruskal 為常用解法之一。C 正確，依切集性質（cut property），跨越某一切集且權重最小的邊必屬於最小展開樹；在邊權重皆相異時最小展開樹唯一，該最小權重邊一定被包含。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。