問題詳情

35.關於最小成本擴張樹(MinimumSpanningTrees，MST)的敘述，下列何者正確？
(A)MST是指為一個Connected無向圖找尋可以連接所有點，且不形成循環的權重和最小邊所形成的樹，是一種GreedyAlgorithm
(B)一般常採用Prim’sAlgorithm或Kruskal’sAlgorithm計算MST
(C)Prim’sAlgorithm的解題要件是由擴張樹的所有邊中，挑選出具最小值且不形成迴路者逐一加入，其時間複雜度為O(nlogn)
(D)因為所有成本最小，故在MST中各頂點之間距離一定是ShortestPath。

參考答案

答案：A,B
難度：非常困難0.1
書單：沒有書單，新增