建立如下無向圖（Undirected Graph）之最小生成樹（Minimum Spanning Tree），其各邊權重總和為多少？

題目

建立如下無向圖（Undirected Graph）之最小生成樹（Minimum Spanning Tree），其各邊權重總和為多少？ A. 45 B. 48 C. 52 D. 53

官方答案

• 答案：C. 52

解析

無向圖之最小生成樹（MST）可利用 Kruskal 演算法或 Prim 演算法求解。依演算法步驟，依各邊權重由小至大依序挑選，且避免形成封閉迴路（Cycle），直到將圖中所有頂點完全連通。將所選取的生成樹邊集合之各邊權重加總，其最小權重總和為 52，故正確答案選 C。A（45）、B（48）權重過小不足以使全圖節點連通，D（53）則非最小權重組合。

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

官方資料

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

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