4

私が使用した擬似コード： 

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行目ごとに2行目と4行目は、すべてのエッジを1つずつlog E追加/削除しているため、時間がかかります。PQ

したがって、合計time= V-1+2E.logE=E.log E

しかし、本はそれがそうだと言っていE.logVます、それがなぜであるか説明できますか？

4

2 に答える 2

1

s に付随するすべてのエッジ e(s,t) に対して

ノードは最大いくつのエッジを持つsことができますか?
V-1せいぜい。したがって、PQ 操作の時間の複雑さは O(logV) です。

于 2009-08-22T10:15:33.173 に答える