Priority Q を使用した ElogV の Prim のアルゴリズムの時間計算量はどのくらいですか?

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)) です

Answer 2

  

すべてのエッジeの（s、t）はSに入射

ノードsは、最大でどのように多くのエッジを持つことができますか？
せいぜいV-1。だから、PQの操作はO（logV）時間の複雑さを持っています。