Calculadora Algoritmo de Prim

Pseudocódigo

Prim hace crecer un único árbol desde un inicio arbitrario. En cada paso toma la arista más barata con exactamente un extremo ya dentro del árbol.

Prim(grafo, inicio):
    enArbol = {inicio}
    cp = cola de prioridad con las aristas que salen de inicio
    mst = []

    mientras enArbol no contenga todos los vértices:
        (u, v, w) = cp.extraerMínimo()
        si v en enArbol: continuar    // obsoleta

        mst.añadir((u, v, w))
        enArbol.añadir(v)
        para cada arista (v, x, w2):
            si x no en enArbol: cp.insertar((v, x, w2))

La corrección descansa en la propiedad del corte: para cualquier partición de los vértices en dos lados, la arista más barata que cruza ese corte pertenece a algún árbol de expansión mínimo. Prim la aplica con el corte "ya en el árbol" frente a "todavía no", y por eso tomar la arista más barata que cruza siempre es seguro y nunca hace falta retroceder.

Ejemplo resuelto, paso a paso

Haz crecer un árbol de expansión mínimo desde A en un pequeño grafo con pesos donde la elección voraz rechaza deliberadamente una arista directa aparentemente más barata.

Grafo de ejemplo: Aristas no dirigidas A-B (2), A-C (3), B-C (1), C-D (4) y B-D (7).

1. Empezar en A. El árbol solo contiene A. Las aristas que salen son A-B con 2 y A-C con 3.
2. Tomar A-B (2). A-B es la arista de cruce más barata, así que B entra en el árbol. La frontera pasa a contener A-C con 3, B-C con 1 y B-D con 7.
3. Tomar B-C (1). B-C con 1 es ahora la arista de cruce más barata, más que la directa A-C con 3, así que C entra a través de B. La arista directa A-C nunca se usa. Este es el paso que conviene observar: un vértice adyacente al inicio no está necesariamente conectado a través del inicio.
4. A-C pasa a ser interna. Con A y C ya en el árbol, la arista A-C tiene ambos extremos dentro y se descarta cuando aflora. Eso es la comprobación de entradas obsoletas cumpliendo su función.
5. Tomar C-D (4). Las aristas de cruce restantes son C-D con 4 y B-D con 7. C-D es más barata, así que D se une y el árbol abarca los cuatro vértices.

El árbol de expansión mínimo es A-B, B-C y C-D con peso total 2 + 1 + 4 = 7. Fíjate en que tiene exactamente tres aristas, una menos que los cuatro vértices, como debe ocurrir en todo árbol de expansión. Fíjate también en que aquí el árbol es un camino, lo que recuerda que un árbol de expansión mínimo no es un árbol de caminos mínimos: los dos problemas optimizan cosas distintas.

Complejidad y de dónde sale

Tiempo: O(E log V) · Espacio: O(V + E)

Con un montículo binario, cada arista puede insertarse una vez y extraerse una vez a O(log E), y como E es a lo sumo V al cuadrado, log E queda dentro de un factor constante de log V, lo que da O(E log V). Cada vértice se añade al árbol exactamente una vez. Un montículo de Fibonacci con reducción de clave en lugar de inserción perezosa mejora la cota a O(E + V log V), asintóticamente mejor en grafos densos aunque rara vez compense por las constantes. En un grafo muy denso gana la opción más simple: mantener un vector con la arista más barata hacia cada vértice exterior y recorrerlo cada ronda, con O(V al cuadrado), que supera a O(E log V) en cuanto E se acerca a V al cuadrado.

Cuándo usar Algoritmo de Prim y cuándo no

Prim y Kruskal producen ambos un árbol de expansión mínimo. El adecuado depende de la densidad y de cómo llegan las aristas.

Errores frecuentes

• Confundir un árbol de expansión mínimo con un árbol de caminos mínimos. Son objetivos distintos. Un MST minimiza el peso total de todo el árbol; un árbol de caminos mínimos minimiza la distancia desde un origen a cada vértice. En el ejemplo anterior el camino del MST de A a D cuesta 7 en aristas del árbol, y en general un MST puede dejar pares concretos mucho más lejos de lo necesario.
• Omitir la comprobación de entradas obsoletas. Un montículo perezoso acumula aristas cuyo extremo lejano acaba entrando en el árbol por otra ruta. Sacar una de ellas y añadirla crea un ciclo y rompe el árbol. Comprueba siempre si el destino ya está en el árbol antes de aceptar una arista.
• Ejecutarlo sobre un grafo desconectado. Prim hace crecer un árbol desde un inicio y termina cuando no encuentra ninguna arista de cruce. En un grafo desconectado devuelve un árbol de expansión de una sola componente. Si necesitas un bosque de expansión mínimo, reinicia desde cada vértice no visitado, o usa Kruskal, que lo maneja de forma natural.
• Suponer que el MST es único. Cuando varias aristas comparten peso puede haber muchos árboles de expansión mínimos, todos con el mismo total. El árbol es único solo si todos los pesos son distintos. Las pruebas deberían comparar el peso total, no el conjunto de aristas.
• Aplicarlo a un grafo dirigido. Los árboles de expansión tal como los definen Prim y Kruskal son nociones no dirigidas. El análogo dirigido es la arborescencia de expansión mínima, que requiere el algoritmo de Chu-Liu/Edmonds; Prim da respuestas incorrectas allí.

Preguntas frecuentes

¿Para qué sirve el algoritmo de Prim?

Encuentra un árbol de expansión mínimo: el conjunto de aristas más barato que conecta todos los vértices de un grafo no dirigido con pesos. Se usa para diseñar redes de bajo coste, como redes eléctricas, tendidos de fibra y telecomunicaciones, canalizaciones de agua y trazado de circuitos, y también sustenta el agrupamiento de enlace simple y algunos métodos de segmentación de imágenes.

¿Cuál es la complejidad temporal del algoritmo de Prim?

O(E log V) con un montículo binario, que es la implementación habitual. Un montículo de Fibonacci da O(E + V log V), asintóticamente mejor en grafos densos pero con peores constantes. En grafos muy densos, un simple recorrido de vector con O(V al cuadrado) es en realidad más rápido porque evita del todo el coste del montículo.

¿Cuál es la diferencia entre el algoritmo de Prim y el de Kruskal?

Prim hace crecer un único árbol conectado hacia afuera desde un vértice inicial, añadiendo siempre la arista más barata que alcanza un vértice nuevo. Kruskal ordena todas las aristas y añade cualquiera que no cierre un ciclo, haciendo crecer un bosque que acaba fundiéndose en un árbol. Prim encaja con grafos densos, Kruskal con grafos dispersos o con aristas ya ordenadas, y ambos dan un árbol de expansión mínimo.

¿Es lo mismo un árbol de expansión mínimo que un árbol de caminos mínimos?

No. Un MST minimiza el peso total de sus aristas; un árbol de caminos mínimos minimiza la distancia desde un origen a cada vértice. A menudo difieren, y un MST puede dejar dos vértices muy alejados en distancia dentro del árbol aunque exista una arista directa corta, porque usarla elevaría el total.

¿Cambia el resultado según el vértice de partida?

Puede cambiar qué aristas se eligen cuando hay pesos empatados, pero nunca el peso total. Prim produce un árbol de expansión mínimo desde cualquier inicio. Si todos los pesos son distintos, el árbol es único y el vértice de partida no influye en absoluto.