關於 Kruskal 最小展開樹（minimum spanning tree）演算法，下列敘述何者錯誤？
A屬於貪心演算法（greedy algorithm）
B若圖中存在相同權值的邊，則無法找出最小展開樹正確答案
C必須先將圖中所有的邊依權值從小到大排序
D針對同一個圖，Kruskal 演算法和 Prim 演算法找出的最小展開樹有可能不同
答案與詳解
B
正確答案
Kruskal 是貪心法，依權值排序挑邊，相同權值仍可找出 MST，只是可能有多組解。
為什麼答案是 B
錯誤敘述即為答案。相同權值的邊存在時，Kruskal 仍能找出最小展開樹，只是 MST 可能不唯一（有多組合法解），並非找不到。
載入中…
完整詳解
Pro · 無限重點 Kruskal 是貪心法，依權值排序挑邊，相同權值仍可找出 MST，只是可能有多組解。
秒殺技巧
看到「無法」「不能」這種絕對化敘述，多半是錯的。相同權值只是解不唯一，不是找不到。逐選項分析
A✕
Kruskal 每次挑選「目前最小且不形成環」的邊，屬於典型貪心演算法，此敘述正確。
B✓ 正確
錯誤敘述即為答案。相同權值的邊存在時，Kruskal 仍能找出最小展開樹，只是 MST 可能不唯一（有多組合法解），並非找不到。
C✕
Kruskal 的第一步就是把所有邊依權值由小到大排序，再依序挑選不形成環的邊，此敘述正確。
D✕
當圖中存在相同權值邊時，MST 可能有多組解，Kruskal 與 Prim 挑選順序不同，結果可能不同（但總權值相同），敘述正確。
Kruskal vs Prim 比較
| 項目 | Kruskal | Prim |
|---|---|---|
| 策略 | 貪心 (選最小邊) | 貪心 (擴張最近點) |
| 資料結構 | Union-Find + 排序 | Priority Queue |
| 時間複雜度 | O(E log E) | O(E log V) |
| 適用圖 | 稀疏圖較佳 | 稠密圖較佳 |
| 起點 | 不需起點 | 需指定起點 |
陷阱提醒
B 選項把「解不唯一」偷換成「無法找出」。相同權值邊只會讓 MST 有多組合法答案，演算法仍能正常運作並找出其中一組最佳解，千萬別被「無法」兩字騙了。