使用優先級隊列的Prims算法的複雜性？

Question

我正在使用一個鄰接矩陣，優先級隊列是數據結構。

通過我的計算，複雜度是V^3 log V：

• While循環：V
• 檢查相鄰的頂點：V
• 檢查條目是否已經存在，並更新相同的隊列：V log v

但是，我到處讀到複雜度爲V^2

請說明。

Answer 1

如果您使用斐波納契堆，則提取最小值爲O(lg V)攤銷成本，並更新其中的條目爲O(1)攤銷。

如果我們用這個僞代碼

while priorityQueue not empty 
    u = priorityQueue.exractMin() 
    for each v in u.adjacencies 
     if priorityQueue.contains(v) and needsWeightReduction(u, v) 
      priorityQueue.updateKeyWeight(u, v) 

假設執行具有一定的時間兩個priorityQueue.contains(v)和needsWeightReduction(u, v)。

需要注意的一點是，您可以爲檢查鄰接關係稍微嚴格一些。雖然外層循環運行V次，並且檢查任何單個節點的鄰接點是最差的V操作，但您可以使用聚合分析來實現您將永遠不會檢查超過E鄰接關係（因爲它們只有E邊緣）。和E <= V^2，所以這是一個稍微好一點的界限。

所以，你有外環V次，內環E次。提取最小分數V次，並更新堆中的條目運行E次。

V*lgV + E*1 
= O(V lgV + E) 

同樣，由於E <= V^2你可以利用這一點來替代，並得到

O(V lgV + V^2) 
= O(V^2) 

但是，這是考慮到稀疏圖（雖然正確）當綁定一個寬鬆。