Algoritmo de Prim

Imagina que tiendes cable desde una central eléctrica: conectas primero el pueblo más cercano, luego el pueblo más cercano a cualquier punto ya conectado, y así sucesivamente. Eso es el algoritmo de Prim, y siempre termina con la red más barata posible.

Un grafo con un árbol que crece desde un nodo, los nodos en espera alrededor con sus mejores aristas discontinuas, y debajo la lista de nodos en espera
Un grafo con un árbol que crece desde un nodo, los nodos en espera alrededor con sus mejores aristas discontinuas, y debajo la lista de nodos en espera

La idea

Un árbol de expansión mínima conecta todos los nodos de un grafo ponderado con la menor longitud total de aristas posible. El algoritmo de Prim lo construye haciendo crecer un solo árbol hacia fuera desde un origen. El árbol nunca se parte en trozos: en cada paso entra exactamente un nodo nuevo, por la arista más corta que sale del árbol.

Paso a paso

Pon el origen en el árbol. Para cada nodo fuera del árbol, guarda su mejor arista: su arista más corta hacia cualquier nodo del árbol. Luego repite: elige el nodo de fuera cuya mejor arista es la más corta, añádelo al árbol con esa arista y revisa sus aristas. Un vecino fuera del árbol al que ahora se llega por una arista más corta toma esa arista como su nueva mejor arista. Para cuando todos los nodos estén en el árbol.

Un ejemplo

Toma las aristas A–B de longitud 1, B–C 2, A–C 3, C–D 4 y B–D 5, y empieza en A. Las aristas de A dan a B la mejor arista 1 y a C la mejor arista 3. B es el más cercano, así que entra por A–B; sus aristas mejoran C a 2 y dan 5 a D. C entra por B–C, y su arista C–D mejora D a 4. Por último, D entra por C–D. El árbol A–B, B–C, C–D tiene longitud total 1 + 2 + 4 = 7.

Por qué es correcto

En cada paso los nodos están divididos en dos grupos: los del árbol y los de fuera. La propiedad del corte dice que la arista más corta entre dos grupos así siempre pertenece a algún árbol de expansión mínima. Prim añade siempre justo esa arista, así que el árbol construido hasta ahora siempre se puede completar hasta un árbol de expansión mínima, y cuando han entrado todos los nodos, lo es.

Historia y velocidad

El matemático checo Vojtěch Jarník publicó el algoritmo en 1930. Robert Prim lo redescubrió en Bell Labs en 1957, y Edsger Dijkstra otra vez en 1959. Con los nodos en espera en un montículo binario, el trabajo crece con E log V para V nodos y E aristas; con un simple array es de unos V², lo que es mejor cuando casi todos los pares de nodos están unidos. Con un montículo de Fibonacci es E + V log V.

Pruébalo

Abre la aplicación, haz clic en un nodo para empezar ahí y pulsa Paso. Los nodos del árbol son verdes, los nodos en espera azules, y la mejor arista de cada nodo en espera se dibuja discontinua. Los nodos en espera aparecen bajo el grafo con la longitud de su mejor arista, de la más corta a la más larga: el primero es el siguiente en entrar. Empieza desde nodos distintos y mira cómo cambia el orden mientras el total sigue igual.

Preguntas frecuentes

¿Qué diferencia hay entre el algoritmo de Prim y el de Dijkstra?

Los dos hacen crecer una región desde un origen con una cola de prioridad. Prim ordena un nodo en espera por la longitud de su mejor arista hacia el árbol; Dijkstra, por su distancia completa desde el origen. Prim da un árbol de expansión mínima, Dijkstra un árbol de caminos más cortos.

¿Funciona el algoritmo de Prim con longitudes de arista negativas?

Sí. A diferencia del algoritmo de Dijkstra, Prim solo compara aristas entre sí, así que las longitudes negativas no dan problemas: sigue encontrando un árbol de expansión con el menor total.

¿Y si el grafo no es conexo?

Entonces el algoritmo de Prim se detiene en cuanto ha llegado a todos los nodos que puede: da un árbol de expansión mínima solo del trozo que contiene el origen. Ejecutarlo otra vez desde un nodo aún no alcanzado da un bosque de expansión mínima.

¿Es mejor el algoritmo de Prim o el de Kruskal?

Ninguno gana siempre. Prim va bien con grafos densos y con grafos guardados como listas de vecinos; Kruskal, con grafos dispersos dados como lista de aristas. Los dos encuentran un árbol de la misma longitud total.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Prueba el algoritmo de Prim