El algoritmo de Prim explicado

Mohammed Islam Hadjoudj

Ingeniero experto en investigación de operaciones

1. Introducción al algoritmo de Prim

El algoritmo de Prim construye un árbol de expansión mínima: dado un grafo conexo, no dirigido y ponderado, selecciona un subconjunto de aristas que toca todos los vértices, no contiene ningún ciclo y tiene el menor peso total posible. En un grafo con V vértices, ese subconjunto contiene siempre exactamente V - 1 aristas.

La estrategia consiste en hacer crecer un único árbol hacia fuera. Empieza en cualquier vértice y, repetidamente, asómate por el borde de lo que ya has construido y trae la arista más barata que toque un vértice que aún no posees. Repítelo V - 1 veces y el árbol estará terminado. No hay retroceso y nunca se elimina nada.

Esa descripción suena casi demasiado voraz para ser correcta. Elegir la arista más barata disponible en cada momento, sin mirar hacia delante, es exactamente la estrategia que falla en caminos mínimos en cuanto aparece una arista negativa. Para árboles de expansión mínima no falla, y la razón es un único teorema que conviene entender antes de tocar código.

2. Por qué funciona: la propiedad del corte

Un corte divide los vértices en dos grupos no vacíos. Una arista cruza el corte si sus dos extremos caen en grupos distintos. El teorema que sostiene el algoritmo de Prim es este:

La demostración es breve y merece verse, porque explica el algoritmo entero. Sea e la arista más barata que cruza cierto corte, y supongamos que un árbol de expansión mínima T no la contiene. Añadir e a T crea exactamente un ciclo, y ese ciclo debe cruzar el corte por segunda vez, usando otra arista f. Elimina f. Sigues teniendo un árbol de expansión y, como e era la arista de cruce más barata, su peso no es mayor que el de f, así que el nuevo árbol no es más pesado. Existe por tanto un árbol de expansión mínima que contiene e.

Mira ahora lo que hace el algoritmo de Prim en cada paso. Los vértices que ya están en el árbol forman un lado de un corte, y todo lo demás forma el otro. El algoritmo selecciona la arista más barata que cruza precisamente ese corte. Por la propiedad del corte, cada arista que elige es segura: pertenece a algún árbol de expansión mínima. La elección voraz nunca es una apuesta que sale bien por casualidad, es un teorema aplicado V - 1 veces.

3. Cómo crece el árbol

En concreto, el algoritmo mantiene tres cosas: el conjunto de vértices que ya están en el árbol, un valor key para cada vértice fuera de él y un puntero parent que registra qué vértice del árbol ofreció esa clave.

• key[v] es el peso de la arista individual más barata que conecta v con el árbol actual, o infinito si aún no existe tal arista.
• parent[v] es el vértice del árbol al otro extremo de esa arista. Es lo que te permite emitir al final el árbol real y no solo su peso.

Cada ronda toma el vértice fuera del árbol con la key más pequeña, lo añade junto con la arista hacia su parent y después relaja: para cada vecino w que siga fuera del árbol, si la arista hacia w es más barata que key[w], baja key[w] y reapunta parent[w].

Fíjate bien en lo que representa la clave. Es el peso de una arista, no el coste de un camino. Ese único detalle es lo que separa este algoritmo del de Dijkstra, un punto al que conviene volver una vez que el código esté sobre la página.

4. Ejecución paso a paso

Tomemos el grafo de seis vértices que se usa a lo largo de nuestra guía de árboles de expansión mínima. Sus nueve aristas son:

A-B 4    A-C 1    B-C 2
B-D 5    C-D 6    C-E 7
D-E 2    D-F 8    E-F 3

Empieza en A. En cada ronda, la "frontera" es el conjunto de aristas con exactamente un extremo dentro del árbol, y el algoritmo toma la más barata de ellas.

1. Árbol = {A}. Frontera: A-C (1), A-B (4). La más barata es A-C (1). Añade C.
2. Árbol = {A, C}. Frontera: B-C (2), A-B (4), C-D (6), C-E (7). Observa que B es ahora alcanzable de dos maneras, con 4 a través de A y con 2 a través de C, así que su clave baja a 2. La más barata es B-C (2). Añade B.
3. Árbol = {A, C, B}. Frontera: B-D (5), C-D (6), C-E (7). D es alcanzable con 5 o con 6, así que su clave es 5. La más barata es B-D (5). Añade D.
4. Árbol = {A, C, B, D}. Frontera: D-E (2), C-E (7), D-F (8). La clave de E baja de 7 a 2. La más barata es D-E (2). Añade E.
5. Árbol = {A, C, B, D, E}. Frontera: E-F (3), D-F (8). La clave de F baja de 8 a 3. La más barata es E-F (3). Añade F.

Cinco aristas añadidas para seis vértices, y el algoritmo se detiene. El árbol es A-C (1), B-C (2), B-D (5), D-E (2), E-F (3), con un peso total de 13. Las aristas A-B (4), C-D (6), C-E (7) y D-F (8) no se usan nunca.

Dos momentos de esa traza merecen atención. En la ronda 3 el algoritmo aceptó una arista de peso 5 mientras una arista de peso 2 (D-E) seguía intacta en otro lugar del grafo. Prim no puede tomar D-E todavía porque ninguno de sus extremos está en el árbol, y tomarla dejaría dos fragmentos inconexos en vez de un único árbol en crecimiento. En la ronda 4 la clave de E cayó de 7 a 2 en cuanto D se unió. Las claves solo pueden disminuir, y eso es lo que hace eficiente la implementación con cola de prioridad.

5. Implementación: Prim perezoso y ansioso

Hay dos implementaciones habituales, y la diferencia está en qué contiene la cola de prioridad.

Prim perezoso

La versión más sencilla mete en un montículo mínimo todas las aristas que encuentra y descarta al extraer las entradas que resultan estar obsoletas.

function LazyPrim(Graph, start):
    inTree = set()
    pq = montículo mínimo vacío, ordenado por peso de arista
    mst = []

    visit(start)                    // marcarlo e insertar sus aristas

    while pq no vacía and size(mst) < V - 1:
        (w, u, v) = pq.pop()        // la arista más barata vista
        if v in inTree: continue    // obsoleta: ambos extremos ya en el árbol
        mst.append((u, v, w))
        visit(v)

    return mst

function visit(x):
    inTree.add(x)
    for cada arista (x, y) con peso w:
        if y not in inTree: pq.push((w, x, y))

La línea if v in inTree: continue hace el trabajo de verdad. Es lo que impide un ciclo, y es la razón por la que el montículo puede contener sin peligro entradas obsoletas: simplemente se omiten cuando salen.

Prim ansioso

La versión ansiosa mantiene como mucho una entrada por vértice, la key[v] actual, y la baja in situ con una operación decrease-key. Necesita una cola de prioridad indexada, que es más maquinaria, pero el montículo nunca crece más allá de V entradas en lugar de E.

function EagerPrim(Graph, start):
    for cada vértice v:
        key[v] = Infinity
        parent[v] = Null
    key[start] = 0
    pq = montículo mínimo indexado de todos los vértices, por key[]

    while pq no vacía:
        u = pq.popMin()
        inTree.add(u)
        for cada arista (u, v) con peso w:
            if v not in inTree and w < key[v]:
                key[v] = w                  // el PESO de la arista, no una suma
                parent[v] = u
                pq.decreaseKey(v, w)

    return parent            // parent[] es el árbol

Prefiere Prim ansioso en grafos densos, donde E es mucho mayor que V y mantener cada arista en el montículo se vuelve un derroche. Prim perezoso es perfectamente razonable en grafos dispersos y bastante más fácil de escribir sin errores.

6. Complejidad temporal y espacial

• Prim perezoso, montículo binario: O(E log E) de tiempo. Cada arista puede insertarse y extraerse una vez. Como E < V2, log E está en O(log V), así que suele escribirse O(E log V). Espacio: O(E).
• Prim ansioso, montículo binario indexado: O(E log V) de tiempo, por V extracciones y hasta E operaciones decrease-key, cada una O(log V). Espacio: O(V).
• Prim ansioso, sin montículo, matriz de adyacencia: O(V2) de tiempo buscando el mínimo linealmente. En un grafo denso, donde E se acerca a V2, esto supera a la versión con montículo, porque O(V2) es mejor que O(V2 log V).
• Prim ansioso, montículo de Fibonacci: O(E + V log V), la mejor cota conocida para Prim, ya que decrease-key pasa a costar tiempo constante amortizado. Las constantes son lo bastante grandes como para que rara vez gane en la práctica.

Resumen práctico: montículo binario en grafos dispersos y la simple búsqueda O(V2) sobre matriz en los densos. El montículo de Fibonacci es sobre todo de interés teórico.

7. Prim frente a Dijkstra: una línea de diferencia

Pon el pseudocódigo de Prim ansioso junto al algoritmo de Dijkstra y son casi el mismo programa. Ambos guardan una clave por vértice, ambos extraen repetidamente el mínimo, ambos relajan los vecinos de lo que acaban de extraer. Toda la diferencia está en qué entra en la clave:

Prim:      if w < key[v]:              key[v] = w
Dijkstra:  if key[u] + w < key[v]:     key[v] = key[u] + w

La clave de Prim es el peso de una sola arista. La de Dijkstra es la longitud acumulada de un camino entero desde el origen. Por eso responden preguntas distintas: Prim pregunta "cuál es la forma más barata de enganchar este vértice a mi árbol", y Dijkstra pregunta "cuál es la forma más barata de llegar a este vértice desde el origen".

También explica por qué los pesos negativos rompen uno y no el otro. La corrección de Dijkstra depende de que los costes de camino nunca disminuyan al alargarse el camino, algo que una arista negativa destruye. Prim no suma pesos en ningún momento, así que los pesos negativos son completamente inofensivos para él. Un árbol de expansión mínima está bien definido en un grafo con pesos negativos, y Prim lo encuentra sin modificación alguna.

8. Prim frente a Kruskal

Ambos algoritmos son voraces, ambos se justifican por la propiedad del corte y, en un grafo con pesos distintos, ambos devuelven el mismo árbol. Difieren en qué mantienen conectado por el camino.

• Prim mantiene en todo momento un único árbol conexo y lo hace crecer hacia fuera. Nunca ordena las aristas y necesita una cola de prioridad.
• Kruskal ordena todas las aristas por peso y añade cada una salvo que cierre un ciclo, de modo que mantiene un bosque de fragmentos que solo se funden en un árbol al final. Necesita una estructura union-find.

La regla práctica se sigue de la densidad. El coste de Kruskal lo domina la ordenación, O(E log E), excelente cuando E es pequeño. Prim con matriz de adyacencia corre en O(V2) sin importar el número de aristas, y gana cuando el grafo es denso. Con entrada inconexa hay además una diferencia estructural: Kruskal produce de forma natural un bosque de expansión mínima, mientras que Prim, partiendo de un único vértice, solo abarca la componente de ese vértice, por lo que hay que reiniciarlo una vez por componente.

9. Notas prácticas y errores frecuentes

Cuatro situaciones dan problemas al pasar del caso de libro a datos reales.

• Los pesos empatados significan varias respuestas válidas. Cuando dos aristas comparten peso, el grafo puede tener más de un árbol de expansión mínima, y cuál obtienes depende de cómo rompa empates tu cola de prioridad. Todos son igual de óptimos, así que una prueba que compare con una lista de aristas fija fallará sin motivo. Compara el peso total en su lugar.
• La entrada inconexa falla en silencio. Partiendo de un vértice, Prim abarca solo la componente de ese vértice y se detiene, devolviendo un árbol que parece perfectamente válido. La comprobación es contar: un árbol de expansión de verdad tiene exactamente V - 1 aristas. Menos significa que el grafo era inconexo y que hay que reiniciar desde un vértice no visitado.
• Bucles y aristas paralelas. Un bucle nunca puede cruzar un corte, así que siempre es ignorable. Entre aristas paralelas que unen el mismo par de vértices, solo la más barata puede elegirse. Ninguna de las dos rompe el algoritmo, pero filtrarlas al leer la entrada mantiene el montículo más pequeño.
• Los grafos dirigidos son otro problema por completo. Un árbol de expansión mínima se define para grafos no dirigidos. Alimentar a Prim con aristas dirigidas produce algo sin sentido. El análogo dirigido es una arborescencia de expansión mínima, que se halla con el algoritmo de Edmonds, y es bastante más difícil.

10. Aplicaciones en el mundo real

Los árboles de expansión mínima responden a una pregunta recurrente: ¿cuál es la forma más barata de conectarlo todo sin redundancia? Prim encaja en los casos en que la red crece realmente desde un origen.

Trazado de redes y servicios

Tender cable, fibra, tubería de agua o carretera entre un conjunto fijo de emplazamientos, donde todos deben ser alcanzables y lo que se minimiza es la longitud o el coste total, es la motivación original. El artículo de Prim salió exactamente de este problema en Bell Labs.

Análisis de agrupamiento

Construir el árbol de expansión mínima de un conjunto de puntos y luego eliminar sus aristas más pesadas es el agrupamiento de enlace simple: quitar las k - 1 aristas más pesadas deja exactamente k grupos. El árbol se calcula una vez y de él sale cualquier valor de k.

Aproximación para problemas más duros

El árbol de expansión mínima da una cota inferior para el recorrido del viajante, y duplicar sus aristas produce un recorrido a lo sumo el doble del óptimo en instancias métricas. Es el punto de partida de la construcción de Christofides, que mejora esa garantía a 1,5.

Segmentación de imágenes y generación de laberintos

Si tratas los píxeles como vértices y la disimilitud como peso de arista, la segmentación basada en MST agrupa una imagen en regiones. Ejecuta Prim sobre una rejilla con pesos aleatorios y obtienes un laberinto de aspecto uniforme, razón por la que es un clásico de la generación procedural.

11. Recursos académicos e historia

Como varios algoritmos clásicos de grafos, este se descubrió más de una vez, y el nombre que lleva no es el de quien lo encontró primero.

• Otakar Borůvka (1926) planteó y resolvió primero el problema del árbol de expansión mínima, motivado por electrificar la Moravia rural. Su algoritmo es otro distinto: añade la arista más barata que sale de cada fragmento en rondas paralelas.
• Vojtěch Jarník (1930) publicó el algoritmo que hoy llamamos de Prim, en una carta que respondía a Borůvka. Por eso a veces se le llama con razón algoritmo de Jarník-Prim.
• Robert C. Prim (1957) lo redescubrió de forma independiente en los Bell Laboratories mientras estudiaba el coste de las redes de conexión, y su artículo es el que llegó a un público amplio.
• Edsger W. Dijkstra (1959) lo redescubrió por tercera vez, en el mismo artículo breve que presentó su algoritmo de caminos mínimos, lo cual no es casualidad dado lo cerca que están ambos.

Para el relato definitivo de quién encontró qué y cuándo, consulta la historia del problema de Graham y Hell. Para un tratamiento riguroso con demostraciones completas de la propiedad del corte y de ambos algoritmos, la referencia estándar es Cormen, Leiserson, Rivest y Stein, Introduction to Algorithms, en el capítulo sobre árboles de expansión mínima. Quien quiera saber hasta dónde se ha llevado la complejidad debería mirar el resultado de montículos de Fibonacci de Fredman y Tarjan y el algoritmo casi lineal de Chazelle. Las citas completas figuran al final de este artículo.