Algoritmos y Estructuras de Datos (VJ1215)

Si los pesos de los arcos son enteros entre 1 y P, podemos implementar la cola de prioridad con un array indexado de 1 a P, manteniendo en la posición i una lista doblemente enlazada de elementos con prioridad i.

De ese modo las operaciones que necesitamos realizar con la cola de prioridad pasan a tener coste O(1), teniendo en cuenta que P es constante y por tanto O(P) = O(1).

Por tanto, el coste del algoritmo de Prim pasa a ser O(|E| + |V|).