Como algoritmo de complexidade de tempo de Prim é ElogV usando o Priority Q?

Question

código Pseudo que eu usei:

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;

De acordo com o meu entendimento:

• Linha 1:. Executa V-1 vezes
• Linha 2: Soma de Grau de todos os tempos vértices ... ..que é vezes 2E

Para cada linha 2: Linha 3 e linha 4 take tempo log E porque estamos adicionando / apagando todas as arestas de / para o PQ por um.

time Então Total = V-1+2E.logE = E.log E

Mas o livro diz que é E.logV, você poderia explicar por que é isso?

Answer 1

O (log (V)) e O (log (E)) são os mesmos.

• E é, no máximo, V ² .
• de log (V ² ) = 2 * log (V)
• que é um grupo O (log (V))

Answer 2

Para todas as arestas e (S, T) incidente para s

Como muitas arestas a s nó pode ter no máximo?
V-1 no máximo. Assim, as operações PQ tem O (logV) complexidade de tempo.