有 n 個節點的連通無向圖（Connected Undirected Graph ）G，假設其中每個邊（Edge）都有不同的加權（Weight），今要在 G 中找出一最小展開樹（Minimum Spanning Tree）T，下列敘述何者錯誤？
AT 中會有 n-1 個邊
BKruskal's Algorithm 是一種常用來找最小展開樹的演算法
CT 中一定包含圖 G 中加權最小的邊
D此問題最適合用 Divide and Conquer 的演算法來解正確答案
答案與詳解
為什麼答案是 D
MST 標準解法是『貪婪演算法』(Greedy Algorithm)，如 Kruskal、Prim、Borůvka，而不是 Divide and Conquer（分治法）。此敘述錯誤，為正解。
考點：樹的邊數考點：Kruskal考點：Cut Property考點：演算法策略
載入中…
