下圖為一個無方向性(Undirected)的加權圖(Weighted Graph)，頂點(Vertex)上的數字為其編號，邊(Edge)上的數字代表成本(Cost)，此圖形的最小展開樹(Minimum Spanning Tree)的總成本(Total Cost)是多少？

錯誤選項解析

• ① 15:總成本 15 低於該圖形實際可達到的最小展開樹成本。使用 Kruskal 演算法 或 Prim 演算法 依邊成本由小到大選取，確保不形成迴圈且涵蓋所有頂點後，總和大於 15。
• ② 16:總成本 16 仍非正確結果。在選取過程中若遺漏某條必要邊或誤選了成本較高的邊替換，會導致計算偏差。正確做法需嚴格遵循貪心策略 (Greedy Strategy) 逐步選取最小成本邊。
• ④ 18:總成本 18 高於最小展開樹的實際成本。此錯誤通常來自選取了非必要的高成本邊，或未正確執行迴圈檢測，導致未能達到最小化總權重的目標。