問題詳情
19 有 n 個節點的連通無向圖（Connected Undirected Graph）G，假設其中每個邊（Edge）都有不同的加 權（Weight），今要在 G 中找出一最小展開樹（Minimum Spanning Tree）T，下列敘述何者錯誤？
(A) T 中會有 n-1 個邊
(B) Kruskal’s Algorithm 是一種常用來找最小展開樹的演算法
(C) T 中一定包含圖 G 中加權最小的邊
(D)此問題最適合用 Divide and Conquer 的演算法來解
參考答案
答案：D
難度：困難0.4
書單：沒有書單，新增
用户評論
【老張】評論
通常算最小生成樹的演算法採用：Borůvka's algorithmKruskal's algorithmPrim's algorithm這些都屬於貪婪演算法(Greedy algorithm)