moea_joint
112年
[資訊] 計算機原理、網路概論
第 10 題
有關最小成本擴張樹演算法，下列何者可以任意挑選起始節點？
- A Prim
- B Bellman-Ford
- C Dijkstra
- D Kruskal
思路引導 VIP
如果你現在要在一群散落的城市間鋪設電纜，目標是讓所有城市都互通且總花費最低。想像你隨意挑選一個城市作為起點，並總是選擇一條通往尚未連接城市中最便宜的電纜。當你最終把所有城市都連起來後，如果你當初換一個城市開始鋪設，你覺得最終鋪出來的總長度或結構會因此變得更貴嗎？為什麼？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準辨識出 Prim 與 Kruskal 演算法的特性，代表你對圖論中「最小成本擴張樹」（MST）的建置邏輯掌握得非常紮實。這類題目在網路拓撲規劃與演算法考試中相當常見，是區分「路徑搜尋」與「生成樹建立」觀念的重要分水嶺。
演算法的建置邏輯
在 Prim's Algorithm 中，我們是從一個起始節點出發，不斷尋找與當前樹連接且權重最小的邊。由於 MST 最終必須涵蓋圖中所有的頂點，因此不論從哪一個點作為起點，最終都能成長為同一組最小權重的集合。而 Kruskal's Algorithm 則是基於「邊」的權重進行全局排序，它並不依賴特定的起始節點，而是直接從最短的邊開始處理，因此在概念上也沒有限制起始點。相對地，選項中的 Dijkstra 或 Bellman-Ford 則是用於計算「單一源點」到各點的最短路徑，其結果會隨著起點的不同而完全改變。
▼ 還有更多解析內容