Q111.
有關計算Minimum Spanning Tree 的Kruskal's 演算法之敘述，下列何者正確？
電腦軟體設計共同科目 · 乙級 · Q111
難易度分析
3 / 5
本題要求區分最小生成樹不同演算法的運作特性，需精確掌握貪婪策略的選取順序、中間狀態的結構定義以及演算法的分類，選項中包含易與相似演算法混淆的特徵，屬於基本概念的對比分析。
正確答案：③演算過程中每次都從未加進的邊中選取最低成本者
③ 演算過程中每次都從未加進的邊中選取最低成本者:Kruskal's 演算法的核心步驟即為：每次從尚未加入的邊中挑選權重最小者，並檢查是否會形成環(Cycle)，若不會則加入生成樹中。
錯誤選項解析
- ① 該演算法不一定從具有最低成本(Cost)的邊(Edge)選取:Kruskal's 演算法必定從權重最低的邊開始選取，這是其核心貪婪策略。此選項敘述與演算法實際運作方式相反。
- ② 演算過程中所加進的邊一直維持一個樹(Tree)狀態:演算過程中維持的是森林(Forest)狀態而非單一樹，直到最後才合併成完整的最小生成樹。與 Prim's 演算法不同，後者才始終維持單一樹的擴展。
- ④ 該演算法是一個Dynamic Programming Algorithm:Kruskal's 演算法屬於貪婪演算法(Greedy Algorithm)，而非動態規劃。它透過不相交集(Disjoint Set)資料結構來高效判斷環的存在。
Learning Tip
"Kruskal's 與 Prim's 演算法均用於求解最小生成樹(MST)，但策略不同：Kruskal's 以邊為基礎進行貪婪選取並維護森林，Prim's 則從單一頂點出發逐步擴展樹。常見陷阱是混淆兩者的運作特性，或誤將 Kruskal's 歸類為動態規劃。實務上需注意 Union-Find 資料結構的路徑壓縮優化對時間複雜度的影響。"
學員答題分佈
①該演算法不一定從具有最低成本(Cost)的邊(Edge)選取0%
②演算過程中所加進的邊一直維持一個樹(Tree)狀態0%
③演算過程中每次都從未加進的邊中選取最低成本者0%
④該演算法是一個Dynamic Programming Algorithm0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
相似類型題目
下圖為街道圖，其中方框內數字表城市編號，線段表兩城市間街道之長度有一有線電視網路公司欲舖設地下纜線，將訊號傳送到六個城市為得到最低道路挖掘成本，下列敘述何者是正確？
下圖為一個無方向性(Undirected)的加權圖(Weighted Graph)，頂點(Vertex)上的字母為其編號，邊(Edge)上的數字代表成本(Cost)，此圖形的最小展開樹(Minimum Spanning Tree)的總成本(Total Cost)是多少？
下圖為一個無方向性(Undirected)的加權圖(Weighted Graph)，頂點(Vertex)上的數字為其編號，邊(Edge)上的數字代表成本(Cost)，此圖形的最小展開樹(Minimum Spanning Tree)的總成本(Total Cost)是多少？
下圖為街道圖，其中方框內數字表城市編號，線段表兩城市間街道之長度，有一有線電視網路公司欲舖設地下纜線，將訊號傳送到六個城市，為得到最低道路挖掘成本，下列那一個路段是不必要挖掘？
依下圖從START 節點開始，使用Prim 演算法計算Minimum Spanning Tree 的總成本，何者是正確？