Árboles de expansión mínima: Prim

Qué cubre este capítulo

Los últimos cinco capítulos preguntaban por caminos — la ruta más barata de aquí para allá. Este hace una pregunta distinta: ¿cómo conectas todo lo más barato posible? Dado un grafo con pesos de ciudades, casas o pines de un circuito, encuentra el conjunto de aristas que amarra cada nodo en una sola estructura conectada con el menor peso total. La respuesta es un árbol de expansión mínima (minimum spanning tree): de expansión porque alcanza todos los nodos, árbol porque no tiene aristas redundantes (exactamente V−1, sin ciclos), y mínima porque ningún otro árbol de expansión pesa menos. El algoritmo de Prim construye uno, y es el tercer hermano de Dijkstra y A*: el mismo recorrido con priority queue que expande una frontera hacia afuera, con un solo cambio — el heap se ordena por el peso de la arista en lugar de la distancia al origen. Este capítulo lo construye, ve crecer el árbol una arista más barata a la vez, y muestra que "mínima" vale un factor de tres frente a simplemente conectar las cosas como te vayan cayendo.

Un poco de historia

El algoritmo tiene una historia enredada y redescubierta muchas veces. El matemático checo Vojtěch Jarník lo describió primero, en 1930, para resolver un problema concreto que le planteó un ingeniero eléctrico que trazaba una red eléctrica eficiente en Moravia — así que su origen, como buena parte de la teoría de grafos, es infraestructura física. Robert Prim lo redescubrió de forma independiente en 1957 mientras trabajaba en Bell Labs minimizando el costo de conectar centrales telefónicas, y Edsger Dijkstra lo volvió a redescubrir en 1959, en la misma familia de artículos que su trabajo sobre caminos mínimos, que es justo por lo que los dos algoritmos se parecen tanto — salieron de la misma cabeza al mismo tiempo. En rigor es el algoritmo de Jarník-Prim-Dijkstra, aunque se quedó con el nombre de Prim. Que un problema de redes eficientes lo haya producido tres veces en cuatro décadas te dice qué tan fundamental es: los árboles de expansión mínima son el núcleo matemático de "conecta estas cosas barato", y ese problema nunca deja de importar.

La intuición

Empieza con un solo nodo en tu árbol y todo lo demás afuera. Mira todas las aristas que cruzan la frontera — las que conectan un nodo que ya está en el árbol con uno que sigue afuera — y escoge la más barata. Agrega su extremo de afuera al árbol. Ahora la frontera se movió: el nodo recién agregado trajo sus propias aristas, y algunas cruzan la nueva frontera. Vuelve a mirar todas las aristas que cruzan, escoge la más barata, agrega su extremo. Repite hasta que todos los nodos estén en el árbol. Eso es el algoritmo de Prim completo: siempre extiende el árbol con la única arista más barata que lo haga crecer.

La priority queue es lo que hace rápido eso de "escoge la arista más barata que cruza". Cada vez que agregas un nodo, empujas sus aristas (hacia vecinos que siguen afuera) a un min-heap ordenado por peso; en cada paso sacas la más chica, y si su otro extremo sigue afuera, esa es tu siguiente arista del árbol. Compáralo con Dijkstra, que empujaba al heap la distancia total desde el origen; Prim empuja nada más el peso de esa única arista. Esa es toda la diferencia. Dijkstra hace crecer un árbol de caminos mínimos — cada nodo conectado por su ruta más barata de regreso al origen. Prim hace crecer un árbol de conexiones más baratas — cada nodo pegado por la arista individual más barata que había disponible cuando se unió. La misma frontera que crece hacia afuera, el mismo heap, distinta llave, distinto árbol.

Complejidad: cómo escala

Con un heap binario, Prim es $O(E \log V)$: cada arista se empuja y se saca a lo mucho una vez ($\log V$ cada operación), y cada nodo se extrae una vez. Con un heap de Fibonacci mejora a $O(E + V \log V)$, lo cual importa en grafos muy densos, y una versión simple con barrido de arreglo (sin heap) es $O(V^2)$, la mejor cuando el grafo es casi completo. El espacio es $O(V)$ para las marcas del árbol más el heap. Pero el número que justifica el algoritmo no es su velocidad — es qué tanto más barato es su árbol comparado con un árbol de expansión que ignora los pesos. El enfrentamiento mide exactamente eso: el peso total del árbol de expansión mínima de Prim contra un árbol de expansión arbitrario (el que construye de casualidad un recorrido a lo ancho):

Los dos árboles conectan todos los nodos con exactamente el mismo número de aristas — V−1 — así que son igual de válidos como conexiones. Pero en grafos de 400 nodos el árbol arbitrario del recorrido a lo ancho pesó como tres veces más que el árbol de expansión mínima (más o menos 6200 contra 2000). La misma conectividad, el triple de costo, nada más porque la búsqueda a lo ancho agarra la arista que llegue primero a un nodo mientras que Prim aguanta hasta encontrar la más barata. En una red real — cable, tubería, camino, pista de circuito — ese factor de tres es dinero, o cobre, o latencia. Aquí "mínima" no es una finura matemática; es la diferencia entre una red barata y una desperdiciada, y Prim encuentra la barata en el mismo tiempo en que BFS construye la desperdiciada.

En qué es bueno y en qué no

Prim es la herramienta correcta para problemas de conexión de costo mínimo, sobre todo en grafos densos donde su frontera que barre aristas es eficiente: diseñar redes (redes eléctricas, tuberías de agua y gas, trazados de fibra y cable, interconexión de chips) para enlazar cada sitio al costo total mínimo, y cualquier problema que se reduzca a eso. Los árboles de expansión mínima también son la base del clustering — quita las aristas más caras de un MST y el árbol se cae en grupos fuertemente conectados (el clustering de enlace simple es exactamente esto) — y dan aproximaciones rápidas para problemas difíciles como el del agente viajero. Prim hace crecer un solo árbol, lo cual lo hace un ajuste natural cuando tienes una ubicación semilla desde la cual construir hacia afuera.

Donde Prim es menos natural es en grafos dispersos, donde el enfoque de Kruskal de ordenar aristas (siguiente capítulo) suele ser más simple y competitivo, y en escenarios distribuidos o de streaming, donde las decisiones independientes por arista de Kruskal se paralelizan más fácil que el crecimiento de frontera de Prim, inherentemente secuencial. Un árbol de expansión mínima además responde una pregunta específica — la conexión más barata — que a veces se confunde con los caminos más baratos. El MST no contiene los caminos mínimos entre pares de nodos: la ruta por el árbol entre dos nodos puede ser mucho más larga que su camino mínimo real. Si quieres caminos cortos, eso es Dijkstra; si quieres conectividad total barata, eso es Prim. El mismo grafo, estructuras distintas.

Los datos, o las entradas

El enfrentamiento corre sobre grafos aleatorios conectados con pesos y compara el peso total del árbol de expansión mínima de Prim contra un árbol de expansión arbitrario construido por búsqueda a lo ancho — los mismos nodos, el mismo conteo de V−1 aristas, aislando el efecto de elegir aristas por peso. La corrección se verifica de forma cruzada contra el algoritmo de Kruskal (el método de MST independiente del siguiente capítulo): en cientos de grafos aleatorios el peso total de Prim tiene que ser igual al de Kruskal, y el resultado tiene que tener V−1 aristas que abarquen todos los nodos. La animación corre Prim sobre un grafo pequeño con pesos, dibujando el corte en cada paso — las aristas azules punteadas son las candidatas que cruzan del árbol hacia afuera — y encendiendo la más barata cuando la elige.

Constrúyelo, una función a la vez

El algoritmo completo — un heap de aristas que cruzan, agrega la más barata, empuja las aristas del nodo nuevo:

def prim(adj, n, start=0):
    """Grow a minimum spanning tree from `start`. `adj[u]` is a list of (neighbor, weight).
    Keep a min-heap of candidate edges (weight, from_tree, to_node) that cross from the tree
    to the outside. Repeatedly pull the cheapest crossing edge; if its far end is still
    outside, add that edge to the tree and push the new node's own edges as fresh candidates.
    O(E log V). Returns (mst_edges, total_weight)."""
    in_tree = [False] * n
    in_tree[start] = True
    mst_edges = []
    total = 0
    pq = [(w, start, v) for v, w in adj[start]]   # edges leaving the start node
    heapq.heapify(pq)
    while pq and len(mst_edges) < n - 1:
        w, a, b = heapq.heappop(pq)
        if in_tree[b]:
            continue                              # b already attached — stale crossing edge
        in_tree[b] = True                         # attach b to the tree via the cheapest edge
        mst_edges.append((a, b, w))
        total += w
        for c, wc in adj[b]:                       # b's edges are new candidates across the cut
            if not in_tree[c]:
                heapq.heappush(pq, (wc, b, c))
    return mst_edges, total

Y la cantidad que minimiza, como referencia:

def spanning_tree_weight(edges):
    """Sum the weights of a set of (u, v, w) tree edges — the quantity a minimum spanning
    tree minimizes."""
    return sum(w for _, _, w in edges)

Míralo funcionar

Aquí está Prim haciendo crecer un árbol de expansión mínima desde el nodo 0. Los nodos verdes están en el árbol; los oscuros siguen afuera; el naranja marca el nodo recién agregado. Las aristas cuentan la historia del corte: las azules punteadas cruzan del árbol hacia afuera — son las candidatas —, las grises están completamente fuera del árbol, y las verdes son el árbol mismo. En cada paso, Prim saca la arista más barata que cruza (parpadea en naranja) y agrega su extremo de afuera, lo cual mueve la frontera y revela candidatas nuevas. Fíjate cómo el total acumulado sube la cantidad más chica posible en cada paso — nunca una arista de peso 6 cuando todavía hay una de peso 1 cruzando el corte — hasta que los siete nodos quedan colgados juntos en seis aristas de peso total 15, la conexión más barata posible:

El código completo

La pestaña "desde cero" es Prim con su priority queue; la pestaña de librería es Kruskal — el otro algoritmo de MST, usado aquí como la referencia independiente contra la que se verifica el total de Prim — más el árbol de expansión por BFS que ignora pesos del enfrentamiento, y las llamadas a networkx/scipy que usarías en producción. Cambia entre ellas.

"""Prim's algorithm — connect every node of a weighted graph using the cheapest possible
total length of edges, with no cycles. That subgraph is a MINIMUM SPANNING TREE: spanning
(it touches every node), a tree (V−1 edges, no cycles), and minimum (no other spanning tree
weighs less). It's the answer to "wire up all these houses / cities / components as cheaply
as I can."

Prim's is A* and Dijkstra's twin. It grows a single tree outward from a start node using a
priority queue, and the only thing that changes is WHAT the heap is keyed on. Dijkstra put
g(n) — the total distance from the source — on the heap. Prim puts just the WEIGHT OF THE
EDGE that would attach a new node to the tree. So instead of "which node is closest to the
start," Prim repeatedly asks "which node is cheapest to connect to the tree I have so far,"
adds it, and repeats. Same heap-driven frontier, one word changed, and a shortest-path
traversal becomes a minimum-spanning-tree builder.
"""
import heapq


# region: prim
def prim(adj, n, start=0):
    """Grow a minimum spanning tree from `start`. `adj[u]` is a list of (neighbor, weight).
    Keep a min-heap of candidate edges (weight, from_tree, to_node) that cross from the tree
    to the outside. Repeatedly pull the cheapest crossing edge; if its far end is still
    outside, add that edge to the tree and push the new node's own edges as fresh candidates.
    O(E log V). Returns (mst_edges, total_weight)."""
    in_tree = [False] * n
    in_tree[start] = True
    mst_edges = []
    total = 0
    pq = [(w, start, v) for v, w in adj[start]]   # edges leaving the start node
    heapq.heapify(pq)
    while pq and len(mst_edges) < n - 1:
        w, a, b = heapq.heappop(pq)
        if in_tree[b]:
            continue                              # b already attached — stale crossing edge
        in_tree[b] = True                         # attach b to the tree via the cheapest edge
        mst_edges.append((a, b, w))
        total += w
        for c, wc in adj[b]:                       # b's edges are new candidates across the cut
            if not in_tree[c]:
                heapq.heappush(pq, (wc, b, c))
    return mst_edges, total
# endregion


# region: total_weight
def spanning_tree_weight(edges):
    """Sum the weights of a set of (u, v, w) tree edges — the quantity a minimum spanning
    tree minimizes."""
    return sum(w for _, _, w in edges)
# endregion

"""The library counterpart, an independent reference, and the contrast. In production a
minimum spanning tree comes from networkx or scipy:

    import networkx as nx
    T = nx.minimum_spanning_tree(G, weight="weight")   # Kruskal by default
    total = T.size(weight="weight")

To check Prim without a third-party dependency, the trace generator uses KRUSKAL below —
the *other* classic MST algorithm (next chapter), which builds the tree a completely
different way: sort all edges cheapest-first and add each one that doesn't form a cycle,
using union-find. Prim grows one tree from a seed; Kruskal merges a forest. They can pick
different trees, but the total weight of a minimum spanning tree is the same however you
build it — so Kruskal's total is the ground truth for Prim's.

`bfs_spanning_tree` is the contrast: *a* spanning tree that ignores weight, to show how much
"minimum" actually saves over just connecting everything however you happen to reach it.
"""
from collections import deque


# region: kruskal
def kruskal(adj, n):
    """MST by Kruskal's method: sort edges ascending, add any that joins two different
    components (union-find), skip any that would close a cycle. Independent of Prim, so it's
    the reference for Prim's total weight."""
    edges = set()
    for u in range(n):
        for v, w in adj[u]:
            edges.add((w, min(u, v), max(u, v)))
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total, picked = 0, []
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            total += w
            picked.append((u, v, w))
    return picked, total
# endregion


# region: arbitrary
def bfs_spanning_tree(adj, n, start=0):
    """*A* spanning tree — the one BFS happens to build, taking whatever edge first reaches
    each node, weight be damned. Same node count, same connectivity, but no attempt to
    minimize total weight. The baseline a minimum spanning tree improves on."""
    seen = [False] * n
    seen[start] = True
    q = deque([start])
    total, picked = 0, []
    while q:
        u = q.popleft()
        for v, w in adj[u]:
            if not seen[v]:
                seen[v] = True
                total += w
                picked.append((u, v, w))
                q.append(v)
    return picked, total
# endregion

Desde cero vs librería

La comparación que vale la pena hacer aquí es Prim contra su propia familia. Es el gemelo de Dijkstra — el mismo recorrido con priority queue, que difiere nada más en la llave del heap — lo cual es una ilustración bonita de que un cambio pequeño a un algoritmo conocido puede responder una pregunta completamente distinta. Y es el rival de Kruskal: dos algoritmos que construyen árboles de expansión mínima con estrategias opuestas (Prim hace crecer un árbol desde una semilla; Kruskal fusiona un bosque de muchos), y aun así siempre llegan al mismo peso total, porque los dos son solo la propiedad del corte aplicada a través de cortes distintos. Que la verificación de corrección pueda validar a Prim contra Kruskal — dos métodos independientes que coinciden — es en sí la lección: cuando un problema tiene un óptimo bien definido, algoritmos correctos distintos convergen en él, y verificar uno contra otro es una prueba más fuerte que cualquiera contra sí mismo. En producción llamarías a networkx.minimum_spanning_tree o scipy.sparse.csgraph.minimum_spanning_tree; construir Prim tú mismo es lo que hace que "es Dijkstra con otra llave" sea algo que ya viste, no algo que te contaron.

Dónde te lo vas a encontrar de verdad

Los árboles de expansión mínima son las matemáticas de la conexión barata, así que Prim corre en cualquier lugar donde se diseñen redes para enlazar todo al menor costo: trazado de redes eléctricas y de telecomunicaciones (su propósito original), redes de tuberías de agua y gas, ruteo de fibra y cable, e interconexión de chips y minimización de pistas de PCB en diseño de hardware. Es un caballito de batalla del clustering — el clustering jerárquico de enlace simple construye un MST y corta sus aristas más pesadas, y los métodos basados en MST segmentan imágenes y agrupan datos. Da una 2-aproximación para el problema métrico del agente viajero, sembrando la optimización de rutas. Aparece en el análisis de confiabilidad de redes, en la generación de laberintos (un MST con pesos aleatorios es un laberinto perfecto), y en el reconocimiento de escritura a mano y de gestos. Donde sea que la tarea sea "conecta todo esto lo más barato posible", un árbol de expansión mínima es la respuesta y Prim es una de las dos formas de construirlo.

Puntos clave

El algoritmo de Prim construye un árbol de expansión mínima — el conjunto de aristas más barato que conecta todos los nodos — agregando repetidamente la arista de menor peso que cruza del árbol hacia afuera, usando una priority queue, en $O(E \log V)$. Es Dijkstra con un cambio, el heap ordenado por peso de arista en lugar de distancia al origen, y su regla avara es demostrablemente óptima gracias a la propiedad del corte: la arista más barata que cruza cualquier corte pertenece a algún árbol de expansión mínima. Su árbol es varias veces más barato que un árbol de expansión arbitrario, pero no es un árbol de caminos mínimos — una conexión total barata es una estructura distinta a rutas individuales cortas.

El siguiente capítulo construye el mismo árbol de expansión mínima con la estrategia opuesta. El algoritmo de Kruskal ignora cualquier punto de partida, ordena todas las aristas de más barata a más cara, y agrega cada una que no cree un ciclo — fusionando un bosque de árboles separados en uno solo. Necesita una forma rápida de preguntar "¿esta arista cerraría un ciclo?", que es justo la estructura union-find del bloque de árboles, lo que hace de Kruskal un reencuentro muy satisfactorio de dos hilos de este libro.