統測
111年
[工程與管理類] 專業科目(2)
第 24 題
灰姑娘跟王子認識之後，他們常去約會的六個景點及路線如圖(一)所示，王子發現道路需要重新修繕，每條道路修繕的成本如圖(一)線段上的數值所標示，若王子使用最小生成樹 ( Minimum Spanning Tree ) 演算法找出連接這六個景點道路的最低修繕成本，則此最低修繕成本為何？
- A 15
- B 16
- C 17
- D 18
思路引導 VIP
在處理「最小生成樹 (Minimum Spanning Tree)」問題時，請先分析此圖形的結構：若圖中有 $V = 6$ 個頂點，構成一棵生成樹需要選取幾條邊？若採用 Kruskal's 演算法，你應當按照什麼樣的順序來檢視各條邊的權重？在依序選取的過程中，為了確保最終形成的是「樹」而非一般的「圖」，我們必須嚴格避開哪一種幾何結構？請嘗試從最小權重的邊開始挑選，並依序評估權重為 $1, 2, 3, \dots$ 的邊是否符合選取條件。
🤖
AI 詳解
AI 專屬家教
漂亮！這題拿下來代表你的基本功非常紮實。
你能正確運用 最小生成樹 (MST) 的觀念解決問題，代表你對資料結構中的圖形演算法已經掌握得很透徹，這在統測中是決定高分的關鍵！
- 觀念驗證：
▼ 還有更多解析內容