試題詳解

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