Algoritmo de Prim

Una demostración para el algoritmo de Prim basado en la distancia de Euclidean

En informática, el algoritmo de Prim (también conocido como algoritmo de Jarník) es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico no dirigido ponderado. Esto significa que encuentra un subconjunto de las aristas que forma un árbol que incluye todos los vértices, donde se minimiza el peso total de todas las aristas del árbol. El algoritmo opera construyendo este árbol un vértice a la vez, desde un vértice inicial arbitrario, en cada paso agregando la conexión más económica posible del árbol a otro vértice.

El algoritmo fue desarrollado en 1930 por el matemático checo Vojtěch Jarník y luego redescubierto y vuelto a publicar por los informáticos Robert C. Prim en 1957 y Edsger W. Dijkstra en 1959. Por lo tanto, a veces también se le llama Jarník' algoritmo;s, algoritmo Prim-Jarník, algoritmo Prim-Dijkstra o el algoritmo DJP.

Otros algoritmos conocidos para este problema incluyen el algoritmo de Kruskal y el algoritmo de Borůvka. Estos algoritmos encuentran el bosque de expansión mínimo en un gráfico posiblemente desconectado; por el contrario, la forma más básica del algoritmo de Prim solo encuentra árboles de expansión mínimos en gráficos conectados. Sin embargo, al ejecutar el algoritmo de Prim por separado para cada componente conectado del gráfico, también se puede usar para encontrar el bosque de expansión mínimo. En términos de su complejidad temporal asintótica, estos tres algoritmos son igualmente rápidos para gráficos dispersos, pero más lentos que otros algoritmos más sofisticados. Sin embargo, para gráficos que son lo suficientemente densos, el algoritmo de Prim puede ejecutarse en tiempo lineal, cumpliendo o mejorando los límites de tiempo de otros algoritmos.

El algoritmo de Prim comienza en el vértice A. En el tercer paso, los bordes BD y AB tienen peso 2, por lo que BD es elegido arbitrariamente. Después de ese paso, AB ya no es un candidato para añadir al árbol porque vincula dos nodos que ya están en el árbol.

Descripción

El algoritmo puede describirse de manera informal realizando los siguientes pasos:

En más detalle, puede implementarse siguiendo el pseudocódigo a continuación.

Como se describió anteriormente, el vértice de inicio del algoritmo se elegirá arbitrariamente, porque la primera iteración del ciclo principal del algoritmo tendrá un conjunto de vértices en Q que tienen pesos iguales, y el algoritmo iniciará automáticamente un nuevo árbol en F cuando complete un árbol de expansión de cada componente conectado del gráfico de entrada. El algoritmo se puede modificar para comenzar con cualquier vértice s en particular configurando C[s] para que sea un número más pequeño que los otros valores de < i>C (por ejemplo, cero), y se puede modificar para encontrar solo un árbol de expansión único en lugar de un bosque de expansión completo (que coincide más estrechamente con la descripción informal) deteniéndose cada vez que encuentra otro vértice marcado como que tiene sin borde asociado.

Las diferentes variaciones del algoritmo difieren entre sí en la forma en que se implementa el conjunto Q: como una lista enlazada simple o una matriz de vértices, o como una estructura de datos de cola de prioridad más complicada. Esta elección conduce a diferencias en la complejidad temporal del algoritmo. En general, una cola de prioridad será más rápida para encontrar el vértice v con un costo mínimo, pero implicará actualizaciones más costosas cuando el valor de C[w] cambios.

Complejidad del tiempo

La complejidad temporal del algoritmo de Prim depende de las estructuras de datos utilizadas para el gráfico y para ordenar los bordes por peso, lo que se puede hacer mediante una cola de prioridad. La siguiente tabla muestra las opciones típicas:

Estructura de datos de peso de borde mínimo	Complejidad del tiempo (total)
matriz de adyacencia, búsqueda	${displaystyle O {fnMicrosoft Sans Serif}$
montón binaria y lista de adyacency	${displaystyle O((las personas que viven en la vida eterna)log vulneró la vida!$
Fibonacci heap and adjacency list	${displaystyle O(Principalidad para la vida y la vida eterna)}$

Una implementación simple de Prim's, usando una matriz de adyacencia o una representación gráfica de lista de adyacencia y buscando linealmente una matriz de pesos para encontrar el borde de peso mínimo para agregar, requiere O(|V|^{2< /sup>) tiempo de ejecución. Sin embargo, este tiempo de ejecución se puede mejorar en gran medida mediante el uso de montones para implementar la búsqueda de bordes de peso mínimo en el bucle interno del algoritmo.}

Una primera versión mejorada usa un montón para almacenar todos los bordes del gráfico de entrada, ordenados por su peso. Esto conduce a un tiempo de ejecución en el peor de los casos O(|E| log |E|). Pero almacenar vértices en lugar de bordes puede mejorarlo aún más. El montón debe ordenar los vértices por el peso de borde más pequeño que los conecta a cualquier vértice en el árbol de expansión mínimo (MST) parcialmente construido (o infinito si no existe tal borde). Cada vez que se elige un vértice v y se agrega al MST, se realiza una operación de tecla decreciente en todos los vértices w fuera del MST parcial tal que v está conectado a w, configurando la clave al mínimo de su valor anterior y el costo de borde de (v,w).

Usando una estructura de datos de montón binario simple, ahora se puede mostrar que el algoritmo de Prim se ejecuta en el tiempo O(|E| log |V|) donde |E| es el número de aristas y |V| es el número de vértices. Usando un montón de Fibonacci más sofisticado, esto se puede reducir a O(|E| + |V| log |V|), que es asintóticamente más rápido cuando el gráfico es lo suficientemente denso como para que |E| es ω(|V|), y el tiempo lineal cuando |E| es al menos |V| registro |V|. Para gráficos de densidad aún mayor (que tengan al menos |V|^c bordes para algunos c > 1), el algoritmo de Prim se puede hacer que se ejecute en tiempo lineal de manera aún más simple, mediante el uso de un montón d-ary en lugar de un montón de Fibonacci.

Demostración de la prueba. En este caso, el gráfico Y₁ = Y − f + e ya es igual a Y. En general, es posible que sea necesario repetir el proceso.

Prueba de corrección

Sea P un gráfico ponderado conexo. En cada iteración del algoritmo de Prim, se debe encontrar una arista que conecte un vértice en un subgrafo con un vértice fuera del subgrafo. Dado que P está conectado, siempre habrá un camino a cada vértice. La salida Y del algoritmo de Prim es un árbol, porque el borde y el vértice agregados al árbol Y están conectados. Sea Y₁ un árbol de expansión mínimo del grafo P. Si Y₁=Y entonces Y es un árbol de expansión mínimo. De lo contrario, sea e el primer borde agregado durante la construcción del árbol Y que no está en el árbol Y₁, y V el conjunto de vértices conectados por las aristas añadidas antes de la arista e. Entonces un extremo del borde e está en el conjunto V y el otro no. Dado que el árbol Y₁ es un árbol de expansión del gráfico P, hay una ruta en el árbol Y₁ uniendo los dos extremos. A medida que uno viaja a lo largo del camino, debe encontrar una arista f que une un vértice en el conjunto V con uno que no está en el conjunto V. Ahora, en la iteración cuando se agregó el borde e al árbol Y, también se podría haber agregado el borde f y se agregaría en lugar del borde e si su peso fuera menor que e, y dado que no se agregó el borde f, concluimos que

${displaystyle w(f)geq w(e).}$

Sea el árbol Y₂ el gráfico obtenido quitando la arista f y añadiendo la arista e al árbol Y₁. Es fácil mostrar que el árbol Y₂ está conectado, tiene el mismo número de aristas que el árbol Y₁, y el peso total de sus aristas no es mayor que el del árbol Y₁, por lo tanto, también es un árbol de expansión mínima del gráfico P y contiene la arista e y todas las aristas añadidas antes de ella durante la construcción del conjunto V. Repita los pasos anteriores y finalmente obtendremos un árbol de expansión mínimo del gráfico P que es idéntico al árbol Y. Esto muestra que Y es un árbol de expansión mínimo. El árbol de expansión mínimo permite que el primer subconjunto de la subregión se expanda en un subconjunto más pequeño X, que suponemos que es el mínimo.

Algoritmo paralelo

La matriz adyacency se distribuyó entre varios procesadores para el algoritmo paralelo de Prim. En cada iteración del algoritmo, cada procesador actualiza su parte de C inspeccionando la fila del vertex recién insertado en su conjunto de columnas en la matriz de adjacency. Luego se recogen los resultados y se selecciona el siguiente vértice para incluir en el MST a nivel mundial.

El bucle principal del algoritmo de Prim es inherentemente secuencial y, por lo tanto, no se puede paralelizar. Sin embargo, el bucle interno, que determina el siguiente borde de peso mínimo que no forma un ciclo, se puede paralelizar dividiendo los vértices y bordes entre los procesadores disponibles. El siguiente pseudocódigo demuestra esto.

Este algoritmo se puede implementar generalmente en máquinas distribuidas, así como en máquinas de memoria compartidas. El tiempo de funcionamiento es ${displaystyle O({tfrac Oh, Dios mío.$, suponiendo que el reducción y difusión operaciones se pueden realizar en ${displaystyle O(log ANTERIOR ANTERIOR)}$. También se ha explorado una variante del algoritmo de Prim para las máquinas de memoria compartida, en la que se está ejecutando el algoritmo secuencial de Prim en paralelo, a partir de diferentes vértices. No obstante, cabe señalar que existen algoritmos más sofisticados para resolver el problema de los árboles mínimos que abarcan de manera más eficiente.