11# Algoritmo de Prim

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

Descripción

El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

Este incrementa continuamente el tamaño de un árbol, comenzando por un vertice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol

El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.

Pseudocodigo

•       Prim(Grafo G)

•       Inicializar todos los vértices y poner el padre de cada vértice en nulo

•       Insertar en la cola de prioridad donde la prioridad es la distancia, todas las parejas <vertice, distancia> del grafo

•       Por cada u en V[G]hacer

•       Distancia[u]=infinito

•       Padre[u]=nulo

•       Añadir (cola,<u,distancia[u]>)

•       Distancia[u]=0

•       Mientras no esté vacia(cola)hacer

•       U= extraer_minimo(cola)//saca el minimo y lo elimina de la cola

•       Por cada v adyacente a u hacer

•       Si((v ∈ cola) && (distancia[v] > peso(u, v)) entonces

•       padre=[v]=u

•       Distancia[v]=peso(u ,v)

•       Actualizar(cola, <v, distancia[v]>)

Árbol de coste mínimo de este árbol

Fuente: Propia