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

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 ²。
• log(V ² ) = 2*log(V)
• 这是一个 O(log(V))