何時爲Prim算法分別使用數組和優先級隊列？

Question

這是一箇舊的考試問題。

在什麼條件下（V，E），我們應該實現使用陣列（由頂點索引）的Prim的 算法的最小優先級的隊列，而不是一個堆（具有對數時間兩者提取物 - 的 實現最小和減少 - 關鍵操作）？

在（V，E）的什麼條件下，我們應該使用有序數組實現Prim的 算法的最小優先級隊列？

Answer 1

當E很大時，最好使用堆作爲優先級隊列，因爲我們將在隊列中有許多節點。從數組O（n）/ O（n）中找到最小/最小值min需要時間，而堆只需要O（1）/ log（n）。

如果E很小，我們將在隊列中有很少的節點，因此，在這種情況下查找min並將其從數組中移除並不需要很多操作。在這種情況下，使用堆不是必需的，由於構建堆所需的操作，它甚至可能比數組慢。

Answer 2

Prim在二進制堆實現中運行於O（mlog（n））時間，m是邊的數量，n是頂點數。然而，當一個圖非常密集時，m非常大，那麼Prim在O（n^2log（n））中運行。您可以創建一個包含大量（n個）頂點的圖形，並將所有頂點連接到彼此以說服您自己。所以......（n-1）+（n-2）+（n-3）......（n-n + 1）。

這可以被重新寫爲

N（N + 1）/ 2，其爲O（n^2）作爲記錄上

優先級隊列數組實現運行在O（N^2）時間這是維基百科頁面記錄在這裏，雖然我沒有證據。

因此，當m很大時最好使用鄰接矩陣。

你問了一個條件，我會說什麼時候m非常大，與n的順序相同。