Árbol de expansión mínima explicado: algoritmos de Kruskal y Prim

Qué problema resuelve un árbol de expansión mínima

Supón que debes conectar varios edificios con cable, varias ciudades con carreteras o varios servidores con enlaces de red, y que cada conexión posible tiene un coste. Quieres que todos los lugares queden conectados (directa o indirectamente) con el menor coste total. Las conexiones sobrantes que forman un bucle nunca hacen falta, así que la respuesta es un árbol: V nodos unidos por exactamente V − 1 aristas. Ese árbol es el árbol de expansión mínima.

Un MST no es un árbol de caminos más cortos. Minimiza el peso total de todas las aristas, no la distancia desde un nodo inicial hasta los demás.

Por qué funciona la decisión voraz: la propiedad del corte

Divide los nodos en dos grupos cualesquiera. Entre las aristas que cruzan de un grupo al otro, la más ligera pertenece a algún árbol de expansión mínima. Ambos algoritmos se apoyan en este hecho:

Si todos los pesos de las aristas son distintos, el MST es único, así que ambos algoritmos devuelven el mismo árbol. Con pesos iguales puede haber varios MST con el mismo total.

Ejemplo resuelto, paso a paso

Grafo no dirigido con 5 nodos y las aristas A–B 4, A–C 3, B–C 1, B–D 2, C–D 4, D–E 2, C–E 5.

Algoritmo de Kruskal, con las aristas ordenadas por peso:

Algoritmo de Prim desde A: la arista más barata que sale de {A} es A–C (3); desde {A, C} es C–B (1); desde {A, B, C} es B–D (2); desde {A, B, C, D} es D–E (2). El mismo árbol, con peso total 3 + 1 + 2 + 2 = 8.

Algoritmo de Kruskal en Python

Union-find guarda un puntero al padre por cada nodo. find devuelve el representante de la componente de un nodo, y dos nodos están conectados exactamente cuando tienen el mismo representante.

def kruskal(nodes, edges):
    parent = {n: n for n in nodes}

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

    tree, total = [], 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:                          # different components: no cycle
            parent[ru] = rv
            tree.append((u, v, w))
            total += w
    return tree, total

nodes = "ABCDE"
edges = [(4, "A", "B"), (3, "A", "C"), (1, "B", "C"), (2, "B", "D"),
         (4, "C", "D"), (2, "D", "E"), (5, "C", "E")]
print(kruskal(nodes, edges))
# ([('B', 'C', 1), ('B', 'D', 2), ('D', 'E', 2), ('A', 'C', 3)], 8)

Un union-find completo también usa unión por rango o por tamaño, que mantiene los árboles poco profundos. Solo con la compresión de caminos por mitades ya es rápido en la práctica. Puedes detener el bucle antes de tiempo cuando el árbol tenga V − 1 aristas.

Algoritmo de Prim en Python

El algoritmo de Prim necesita una lista de adyacencia. Usa eliminación perezosa, como el algoritmo de Dijkstra: inserta cada arista que sale del árbol y omite las aristas cuyo extremo lejano ya está en el árbol.

import heapq
from collections import defaultdict

def prim(edges, start):
    graph = defaultdict(list)
    for w, u, v in edges:
        graph[u].append((w, u, v))
        graph[v].append((w, v, u))
    in_tree = {start}
    heap = list(graph[start])
    heapq.heapify(heap)
    tree, total = [], 0
    while heap:
        w, u, v = heapq.heappop(heap)
        if v in in_tree:
            continue
        in_tree.add(v)
        tree.append((u, v, w))
        total += w
        for edge in graph[v]:
            if edge[2] not in in_tree:
                heapq.heappush(heap, edge)
    return tree, total

print(prim(edges, "A"))
# ([('A', 'C', 3), ('C', 'B', 1), ('B', 'D', 2), ('D', 'E', 2)], 8)

Complejidad temporal y espacial

Como E es como máximo V², log E es como máximo 2 log V, así que O(E log E) y O(E log V) son del mismo orden.

Variantes y errores comunes

• Grafo no conexo: no existe un árbol de expansión. Kruskal devuelve entonces un bosque de expansión mínima (un árbol por componente); Prim desde un solo inicio cubre únicamente la componente de ese inicio. Comprueba que el árbol tenga V − 1 aristas.
• Árbol de expansión máxima: ordena las aristas de mayor a menor (o cambia el signo de los pesos). Los pesos negativos no suponen problema para ninguno de los dos algoritmos.
• Los grafos dirigidos requieren otro algoritmo (arborescencia mínima, Chu-Liu/Edmonds); Kruskal y Prim no se aplican.
• Agrupamiento (clustering): ejecuta Kruskal y detente cuando queden k componentes. El resultado es un agrupamiento de enlace simple en k grupos.
• El algoritmo de Borůvka, de 1926, añade a la vez la arista más barata de cada componente y se paraleliza bien.

Cuándo usarlo y usos en el mundo real

• Diseño de redes: la forma más barata de conectar sedes con cable, tuberías o carreteras, cuando sirve cualquier trazado conexo.
• Algoritmos de aproximación: un MST da un recorrido de como máximo el doble de la longitud óptima para el problema del viajante métrico.
• Agrupamiento y segmentación de imágenes cortando las aristas más pesadas del MST.
• Problemas de entrevista: coste mínimo para conectar todos los puntos, conectar ciudades con coste mínimo, optimizar la distribución de agua en un pueblo.