Algoritmo de Prim

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.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

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.

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.

El algoritmo podría ser informalmente descrito siguiendo los siguientes pasos:

Para hacerlo más en detalle, debe ser implementado el pseudocódigo siguiente.

Como se ha descrito arriba, el vértice inicial para el algoritmo será elegido arbitrariamente, porque la primera iteración del bucle principal del algoritmo tendrá un número de vértices en Q que tendrán todos el mismo tamaño, y el algoritmo empezará automáticamente un nuevo árbol en F cuando complete un árbol de expansión a partir de cada vértice conectado del grafo. El algoritmo debe ser modificado para empezar con cualquier vértice particular s para configurar C[s] para que sea un número más pequeño que los otros valores de C (por norma, cero), y debe ser modificado para solo encontrar un único árbol de expansión y no un bosque entero de expansión, parando cuando encuentre otro vértice con "flag" que no tiene ningún lado asociado.

Hay diferentes variaciones del algoritmo que difieren unas de otras en cómo implementar Q: Como una única Lista enlazada o un vector de vértices, o como una estructura de datos organizada con una cola de prioridades, más compleja. Esta elección lidera las diferencias en complejidad de tiempo del algoritmo. En general, una cola de prioridades será más rápida encontrando el vértice v con el mínimo coste, pero ello conllevará actualizaciones más costosas cuando el valor de C[w] cambie.

//Se utiliza una clase Graph previamente implementada (no existe en Java)

Sea ${displaystyle G}$ un grafo conexo y ponderado.

En toda iteración del algoritmo de Prim, se debe encontrar una arista que conecte un nodo del subgrafo a otro nodo fuera del subgrafo.

Ya que ${displaystyle G}$ es conexo, siempre habrá un camino para todo nodo.

La salida ${displaystyle Y}$ del algoritmo de Prim es un árbol porque las aristas y los nodos agregados a ${displaystyle Y}$ están conectados.

Sea ${displaystyle Y_{1}}$ el árbol recubridor mínimo de ${displaystyle G}$.

Si ${displaystyle Y_{1}=YRightarrow Y}$ es el árbol recubridor mínimo.

Si no, sea ${displaystyle e}$ la primera arista agregada durante la construcción de ${displaystyle Y}$, que no está en ${displaystyle Y_{1}}$ y sea ${displaystyle V}$ el conjunto de nodos conectados por las aristas agregadas antes que ${displaystyle e}$. Entonces un extremo de ${displaystyle e}$ está en ${displaystyle V}$ y el otro no. Ya que ${displaystyle Y_{1}}$ es el árbol recubridor mínimo de ${displaystyle G}$ hay un camino en ${displaystyle Y_{1}}$ que une los dos extremos. Mientras que uno se mueve por el camino, se debe encontrar una arista ${displaystyle f}$ uniendo un nodo en ${displaystyle V}$ a uno que no está en ${displaystyle V}$. En la iteración que ${displaystyle e}$ se agrega a ${displaystyle Y}$, ${displaystyle f}$ también se podría haber agregado y se hubiese agregado en vez de ${displaystyle e}$ si su peso fuera menor que el de ${displaystyle e}$. Ya que ${displaystyle f}$ no se agregó se concluye:

Sea ${displaystyle Y_{2}}$ el grafo obtenido al remover ${displaystyle f}$ y agregando ${displaystyle ein Y_{1}}$. Es fácil mostrar que ${displaystyle Y_{2}}$ conexo tiene la misma cantidad de aristas que ${displaystyle Y_{1}}$, y el peso total de sus aristas no es mayor que el de ${displaystyle Y_{1}}$, entonces también es un árbol recubridor mínimo de ${displaystyle G}$ y contiene a ${displaystyle e}$ y todas las aristas agregadas anteriormente durante la construcción de ${displaystyle V}$. Si se repiten los pasos mencionados anteriormente, eventualmente se obtendrá el árbol recubridor mínimo de ${displaystyle G}$ que es igual a ${displaystyle Y}$.

Esto demuestra que ${displaystyle Y}$ es el árbol recubridor mínimo de ${displaystyle G}$.