Algoritmo de Prim

Robert Prim en 1957 descubrió un algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST). Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka en 1926 mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia. Este problema también fue resuelto por Joseph B. Kruskal en 1956. 

Pasos para su uso

La idea básica consiste en añadir  en cada paso, una arista de peso mínimo  a un árbol previamente construido. Más explícitamente:

Paso 1: se elige un vértice u de G y se considera el árbol s= {u}

Paso 2: se considera la arista e de mínimo peso que une un vértice de s y un vértice que no es de s y se hace s=s+se

Paso 3: si el n° de aristas de t es n-1 el algoritmo termina. En caso contrario se vuelve al paso

Objetivo del

 algoritmo

Encontrar el árbol recubierto más corto

Funcionamiento 

ª El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice 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)
       /* Inicializamos todos los nodos del grafo. 
       La distancia la ponemos a infinito y el padre de cada nodo a NULL
        Encolamos, en una cola de prioridad 
                  donde la prioridad es la distancia, 
               todas las parejas <nodo,distancia> del grafo*/
       por cada u en V[G] hacer
           distancia[u] = INFINITO
           padre[u] = NULL
           Añadir(cola,<u,distancia[u]>)
       distancia[u]=0
       mientras !esta_vacia(cola) hacer
           // OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.
           u = extraer_minimo(cola) //devuelve 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)