問題詳情

11.以有線電視電纜的架設為例，若只能沿著街道佈線，則以街道為邊，而路口為節點，這些邊都有一個數值，代表此邊的成本。我們可以去除圖形中的某些邊，使得剩下的邊能連結所有的節點，何種演算法能使佈線成本最低。
(A)Bellman-FordAlgorithm
(B)DijkstraAlgorithm
(C)Floyd-Warshall
(D)KruskalAlgorithm
(E)PrimAlgorithm

參考答案

答案：D,E
難度：非常困難0.071
書單：沒有書單，新增

用户評論

【用戶】不叫賭俠的陳小刀

【年級】高三下

【評論內容】Kruskal’s Algorithm找到最小生成樹(Minimum Spanning Tree)的一種方法。Kruskal’s Algorithm步驟如下：1. 由小到大排序，所有「邊(Edge)」的權重(Weigh)。2. 從小到大開始取那些「邊(Edge)」，前提是取到的Edge不能形成一個迴圈(loop, cycle)。3. 重複步驟 2的動作，直到最後已經不能再取。普林演算法（Prim's algorithm）是圖論中的一種貪心演算法，可在一個加權連通圖中找到其最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖裡的所有頂點，且其所有邊的權值之和亦為最小。

【用戶】不叫賭俠的陳小刀

【年級】高三下

【評論內容】Kruskal’s Algorithm找到最小生成樹(Minimum Spanning Tree)的一種方法。Kruskal’s Algorithm步驟如下：1. 由小到大排序，所有「邊(Edge)」的權重(Weigh)。2. 從小到大開始取那些「邊(Edge)」，前提是取到的Edge不能形成一個迴圈(loop, cycle)。3. 重複步驟 2的動作，直到最後已經不能再取。普林演算法（Prim's algorithm）是圖論中的一種貪心演算法，可在一個加權連通圖中找到其最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖裡的所有頂點，且其所有邊的權值之和亦為最小。