在執行排序和使用優先隊列之間的Kruskal算法之間的權衡是什麼？

Question

我正在學習Kruskal的算法，並且遇到了幾個不同的實現，並想知道它們之間可能存在什麼折衷。這兩種實現如下：

實現一個 - 把圖中的所有邊緣成一個優先級隊列PQ - 從PQ 除去最小邊e - 如果E連接2先前未連接的圖組分（使用一臺Union查找測試數據結構），然後將其添加到MST - 重複，直到在MST邊數等於圖中頂點總數 - 1

實現兩 - 在圖中的所有邊進行合併排序或快速排序 - 從排序的邊緣數組中刪除最小邊緣 然後按照上述算法

所以唯一真正的區別是在O（eloge）時間內是使用優先級隊列還是先行排序。

這裏的權衡是什麼？兩種實現似乎都有相同的運行時間 - O（ElogV）。我說logV而不是logE，因爲連接的無向圖中邊的最大數量是O（V^2）和logV^2 = 2logV，因此去除常數因子可以減少到O（logV）。

Answer 1

兩個變體都具有相同的漸近複雜性。具有優先級隊列的實現可能會稍微好一些，因爲實際上按重量排序它們可能沒有必要。在找到生成樹之前，只需要最小的邊。剩餘邊的確切順序是無關緊要的。

但是，如果這導致儲蓄完全取決於輸入數據。例如，如果權重最高的邊是最小生成樹的一部分，則必須考慮所有邊。在實踐中，我不會指望有太大的區別。

Answer 2

除了亨利的回答，在實踐中，排序方法的執行還取決於使用哪種排序算法的特定變體。例如。快速排序可以是O（n^2），除非使用昂貴的中值搜索算法（通常不是 - 通常這不會導致問題）。

Mergesort是最壞情況O（n log n）。堆排序也是如此，但其內存訪問非常分散，因此與基本上所有其他排序算法（從中小尺寸輸入或幾乎排序的輸入）相比，它從緩存和RAM突發模式中受益更少，可以使它比快速O（n^2）排序更像插入排序。關於最能說明的一點是，PQ方法應該打敗基於堆排序的排序方法，因爲它對後者的工作有嚴格的限制。