Cómo algoritmo de tiempo complejidad de Prim se ElogV utilizando la prioridad Q?

Question

Pseudo código que utilicé:

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;

Según mi entendimiento:

• línea 1: ejecuta veces V-1
.
• Línea 2: Suma de Grado de todos los tiempos vértices ... ..que es 2E veces

Para cada línea 2: La línea 3 y línea 4 toma el tiempo log E porque estamos añadiendo / eliminando todos los bordes hacia / desde el PQ uno por uno.

Así total de time = = V-1+2E.logE E.log E

Pero el libro dice que es E.logV, podría explicar por qué es así?

Answer 1

O (log (V)) y O (log (E)) son los mismos.

• E es como máximo V ² .
• log (V ² ) = 2 * log (V)
• que es un O (log (V))

Answer 2

  

para todos los bordes e (s, t) incidente a s

¿Cuántas aristas s un nodo puede tener como máximo?
V-1 como máximo. Por lo tanto, las operaciones tienen PQ O (logV) complejidad del tiempo.