Q113.
下圖為一個無方向性(Undirected)的加權圖(Weighted Graph)，頂點(Vertex)上的字母為其編號，邊(Edge)上的數字代表成本(Cost)，此圖形的最小展開樹(Minimum Spanning Tree)的總成本(Total Cost)是多少？
電腦軟體設計共同科目 · 乙級 · Q113
難易度分析
3 / 5
本題需要運用特定演算法對圖形進行分析，經由排除環路並選取最小權重邊的過程，最後進行數值加總，涉及多步驟的邏輯推導與計算。
正確答案：②29
② 29:29 為正確答案。運用 Kruskal 演算法 由小到大選取不會形成環路的邊，或使用 Prim 演算法 從任一頂點逐步擴展，所得到的最小展開樹所有邊成本加總即為 29。
錯誤選項解析
- ① 27:27 低於該加權圖的最小展開樹實際總成本，可能是使用 Kruskal 演算法 或 Prim 演算法 時遺漏了某些必要邊，或未正確排除會形成環路(Cycle) 的邊所致。
- ③ 31:31 高於最小展開樹的實際總成本，可能是選取了成本較大的邊而跳過成本較小的邊，違反了 MST 貪婪演算法(Greedy Algorithm) 選取最小成本邊的原則。
- ④ 33:33 明顯偏高，可能是將所有邊的成本直接加總得到圖的總權重，而非挑選 n-1 條邊構成最小展開樹，或誤算了會形成閉迴路 的邊。
Learning Tip
"最小展開樹(MST) 的核心考點在於掌握 Kruskal 與 Prim 兩種演算法的操作邏輯。常考陷阱包括：(1) 忘記 MST 的邊數必為 頂點數減一(n-1)；(2) 使用 Kruskal 時未正確判斷環路，誤選了會形成閉迴路的邊；(3) 混淆 最短路徑(Shortest Path) 與最小展開樹的概念。實務上需熟練以 Union-Find 資料結構 輔助判斷連通分量。"
學員答題分佈
①270%
②290%
③310%
④330%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
相似類型題目
下圖為一個無方向性(Undirected)的加權圖(Weighted Graph)，頂點(Vertex)上的數字為其編號，邊(Edge)上的數字代表成本(Cost)，此圖形的最小展開樹(Minimum Spanning Tree)的總成本(Total Cost)是多少？
下圖為街道圖，其中方框內數字表城市編號，線段表兩城市間街道之長度有一有線電視網路公司欲舖設地下纜線，將訊號傳送到六個城市為得到最低道路挖掘成本，下列敘述何者是正確？
依下圖從START 節點開始，使用Prim 演算法計算Minimum Spanning Tree 的總成本，何者是正確？
下列有關擴張樹(Spanning Tree)的敘述何者錯誤？
下圖為街道圖，其中方框內數字表城市編號，線段表兩城市間街道之長度，有一有線電視網路公司欲舖設地下纜線，將訊號傳送到六個城市，為得到最低道路挖掘成本，下列那一個路段是不必要挖掘？