algorithm - Prim的算法时间复杂度是ElogV使用Priority Q如何？

Question

我使用的伪代码：

for all V vertices: visited[n]=0

pick any vertex r from graph and set visited[r]=1

For all edges e incident to r
PQ.insert()

while(PQ is not empty)//line 1
  f=PQ.min()//f(r,s) is such that visited[s]=0
  for all edges e(s,t) incident to s//line 2
     if(visited[t]==0)
        PQ.insert(e);//line 3
     else
        PQ.delete(e);//line 4
  visited[s]=1;
end while;

根据我的理解：

• 第 1 行：执行V-1次数。
• 第 2 行：所有顶点的度数之和时间......即2E时间

对于第 2 行：第 3 行和第 4 行需要时间，因为我们正在逐一log E添加/删除所有边缘。PQ

所以总计time= V-1+2E.logE=E.log E

但是书上说是这样E.logV，你能解释一下为什么会这样吗？

Answer 1

O(log(V)) 和 O(log(E)) 是相同的。

• E至多为V ²。
• 对数(V ² ) = 2*对数(V)
• 这是一个 O(log(V))

Answer 2

对于所有与 s 相关的边 e(s,t)

s一个节点最多可以有多少条边？
V-1最多。因此，PQ 操作具有 O(logV) 时间复杂度。