Árboles de expansión mínima: Kruskal

Qué cubre este capítulo

El capítulo pasado construimos un árbol de expansión mínima haciendo crecer un solo árbol desde una semilla. El algoritmo de Kruskal construye el mismo árbol con la filosofía opuesta: olvídate del punto de partida, ordena todas las aristas de la más barata a la más cara, y recorre esa lista agregando cada arista salvo que conecte dos nodos que ya están conectados. Arranca con un bosque de V árboles solitarios de un solo nodo y los va fusionando, arista más barata primero, hasta que todos se unen en uno. La única pregunta que hace una y otra vez —"¿estos dos nodos ya están en el mismo árbol?"— es exactamente lo que la estructura union-find del tier de árboles responde en tiempo casi constante, y eso convierte a Kruskal en la aplicación estrella de esa estructura. Este capítulo lo construye, observa cómo se fusiona el bosque arista por arista, y lo usa para revelar algo que vale la pena ver: en un grafo de un cuarto de millón de aristas, toda la contabilidad de union-find toma menos de dos milisegundos — el costo real de Kruskal es el sort, y union-find prácticamente sale gratis.

Un poco de historia

Joseph Kruskal publicó el algoritmo en 1956, en un artículo corto y elegante en los Proceedings of the American Mathematical Society, un año antes de que Prim redescubriera el de Prim. Es uno de los algoritmos más antiguos cuya corrección se apoya en lo que hoy llamaríamos un argumento de intercambio greedy, y el artículo de Kruskal es admirablemente directo: ordena las aristas, agrega cada una que no forme un ciclo, y demuestra que eso da el mínimo. Lo que el artículo todavía no podía nombrar era la estructura de datos que hace rápida la prueba de ciclos — union-find con compresión de caminos y unión por rango no se analizó hasta los años setenta, de la mano de Robert Tarjan, quien demostró su asombrosa cota amortizada casi constante. Así que el algoritmo de Kruskal es un bonito ejemplo de capas históricas: un método greedy de 1956 cuya eficiencia esperó dos décadas a la estructura de datos de los setenta que lo impulsa. Las dos ideas juntas —una regla greedy simple y una estructura de conjuntos disjuntos rápida— son la razón de que Kruskal sea a la vez fácil de enunciar y rápido de ejecutar.

La intuición

Imagina cada nodo como su propio arbolito — un bosque de V árboles separados de un nodo, sin nada conectado a nada. Ordena todas las aristas por peso, de menor a mayor. Ahora recorre la lista. Para cada arista, pregunta: ¿sus dos extremos ya pertenecen al mismo árbol? Si están en árboles distintos, esta arista une dos piezas separadas del bosque en un árbol más grande — agrégala, y ya es parte de tu árbol de expansión mínima. Si ya están en el mismo árbol, entonces agregar esta arista crearía un ciclo (ya existe un camino entre ellos), así que sáltala. Sigue así hasta que hayas agregado V−1 aristas, momento en el que todo el bosque se ha fusionado en un único árbol de expansión.

¿Por qué de más barata a más cara? Por la propiedad del corte del capítulo pasado: la arista más barata que cruza cualquier división entre piezas conectadas y no conectadas es segura de incluir. Al procesar las aristas en orden, cada arista que Kruskal acepta es la más barata disponible que conecta dos componentes en particular — la propiedad del corte garantiza que pertenece a algún árbol de expansión mínima. La única maquinaria que Kruskal necesita es una forma de saber qué nodos están en qué árbol y de fusionar dos árboles cuando una arista los une, y rápido, porque hace esa prueba una vez por arista. Esa es la estructura union-find (conjuntos disjuntos): find(x) regresa a qué árbol pertenece un nodo, union(a, b) fusiona dos árboles, y con compresión de caminos y unión por rango ambas corren en tiempo efectivamente constante. Kruskal es donde union-find deja de ser un ejercicio abstracto y se vuelve lo que hace rápido a un algoritmo real.

Complejidad: cómo escala

Kruskal es $O(E \log E)$, y ese costo es casi por completo el sort inicial de las aristas. La pasada que sigue —una operación de union-find por arista— es efectivamente $O(E \cdot \alpha(V))$, donde $\alpha$ es la función inversa de Ackermann, que vale a lo mucho 4 para cualquier entrada que vaya a existir. Así que el trabajo de union-find es prácticamente lineal, y el sort domina. El face-off lo vuelve concreto midiendo tres cosas conforme el grafo se hace más denso: Kruskal completo, Prim y —la reveladora— solo la pasada de union-find de Kruskal sobre aristas que ya vienen ordenadas:

Kruskal completo y Prim van codo a codo en todas las densidades — en un grafo de 1500 nodos quedaron a unos cuantos puntos porcentuales, con Prim apenas adelante — así que en la práctica elegir entre ellos casi nunca es cuestión de velocidad. Pero mira la línea de abajo: en el grafo más denso, cerca de un cuarto de millón de aristas, Kruskal completo tomó alrededor de 133 ms mientras que la pasada de union-find sola, sobre aristas pre-ordenadas, tomó menos de 2 ms. El sort es el 98% del trabajo de Kruskal; la detección de ciclos y la fusión son casi gratis. Ese es el premio de las operaciones casi constantes de union-find, y te dice exactamente cuándo gana Kruskal: siempre que las aristas ya estén ordenadas, o se puedan ordenar barato (bucket sort o radix sort sobre pesos enteros), Kruskal baja a casi lineal y le gana a todo.

En qué es bueno y en qué no

Kruskal es la herramienta correcta para árboles de expansión mínima cuando trabajas a partir de una lista de aristas (en lugar de adyacencia), cuando el grafo es disperso, cuando las aristas ya vienen ordenadas o se pueden ordenar barato, o cuando quieres el más amigable al paralelismo de los dos algoritmos clásicos. Su lógica es transparente —ordena, luego agrega-si-no-hay-ciclo— lo que lo vuelve favorito para enseñar y para código donde la corrección es crítica. También es la expresión natural del clustering basado en MST: corre Kruskal pero detente antes, tras V−k fusiones en vez de V−1, y habrás particionado el grafo en exactamente k clusters, cada uno una pieza conectada unida por aristas baratas (esto es single-linkage clustering, y detener Kruskal antes de tiempo es la forma más limpia de verlo).

Donde Kruskal es menos ideal es en grafos densos guardados como estructuras de adyacencia, donde ordenar las $\Theta(V^2)$ aristas es un desperdicio y la frontera de Prim —que solo mira aristas que tocan el árbol actual— hace menos trabajo. También, igual que Prim, produce una estructura que la gente usa mal: un árbol de expansión mínima no es un árbol de caminos más cortos, y el camino dentro del árbol entre dos nodos puede ser mucho más largo que su camino más corto real. Y Kruskal necesita todas las aristas disponibles desde el inicio para ordenarlas, así que no sirve para grafos en streaming donde las aristas llegan con el tiempo y hace falta decidir de inmediato.

Los datos, o las entradas

El face-off corre sobre grafos aleatorios conexos de 1500 nodos con densidad creciente y mide tres estrategias: Kruskal completo (sort + union-find), Prim (cola de prioridad), y solo la pasada de union-find de Kruskal sobre aristas pre-ordenadas — la última aísla qué tan barato es realmente el trabajo de conjuntos disjuntos. La corrección se verifica contra Prim (el algoritmo independiente del capítulo pasado): en cientos de grafos aleatorios el peso total de Kruskal debe ser igual al de Prim, y el resultado debe ser un árbol de expansión de V−1 aristas que alcance todos los nodos. La animación corre Kruskal sobre el mismo grafo pequeño con pesos que Prim resolvió el capítulo pasado (así el total, 15, coincide), coloreando cada nodo según a qué árbol pertenece en ese momento — para que literalmente veas cómo colores separados se fusionan en uno conforme se aceptan aristas.

Constrúyelo, una función a la vez

El motor union-find — la prueba de ciclos en tiempo casi constante que está en el corazón de Kruskal:

class DSU:
    """Disjoint-set union (union-find) with path compression and union by rank — the engine
    that makes Kruskal fast. `find` returns a canonical representative of a node's set;
    `union` merges two sets. Both run in near-constant amortized time (inverse Ackermann),
    so the union-find work across all of Kruskal is effectively linear."""

    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:            # path compression: point everyone at the root
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        """Merge the sets of a and b. Returns False if they were already the same set (so the
        edge would make a cycle), True if a real merge happened."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                         # already connected → adding this edge cycles
        if self.rank[ra] < self.rank[rb]:        # hang the shorter tree under the taller
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

Y Kruskal mismo — ordena, luego agrega cada arista que une dos árboles distintos:

def kruskal(edges, n):
    """Minimum spanning tree by Kruskal's method. `edges` is a list of (u, v, w). Sort all
    edges ascending by weight; for each, add it iff its endpoints are in different components
    (union succeeds). Stop once V−1 edges are chosen. O(E log E) — dominated by the sort;
    the union-find work is effectively linear. Returns (mst_edges, total_weight)."""
    dsu = DSU(n)
    mst_edges = []
    total = 0
    for w, u, v in sorted((w, u, v) for u, v, w in edges):
        if dsu.union(u, v):                      # different trees → safe to add, merges them
            mst_edges.append((u, v, w))
            total += w
            if len(mst_edges) == n - 1:          # a spanning tree is complete at V−1 edges
                break
    return mst_edges, total

Míralo funcionar

Aquí está Kruskal sobre el mismo grafo que Prim construyó el capítulo pasado. Cada nodo está coloreado según a qué árbol pertenece — al inicio los siete tienen colores distintos, siete árboles separados de un nodo. Las aristas se consideran de más barata a más cara: un destello naranja sólido significa "aceptada" (sus extremos tenían colores distintos, así que fusiona dos árboles y adoptan un mismo color), y un destello rojo punteado significa "rechazada" (sus extremos ya tienen el mismo color — mismo árbol — así que formaría un ciclo). Observa cómo se juntan los colores: primero la arista de peso 1, luego la de peso 2, y cada aceptación funde dos colores en uno, hasta que los siete nodos comparten un solo color y el bosque se convirtió en un árbol de peso total 15 — el mismo mínimo que encontró Prim, alcanzado fusionando en lugar de creciendo:

El código completo

La pestaña "desde cero" es Kruskal con su motor union-find; la pestaña de librería es Prim — el algoritmo del capítulo pasado, usado aquí como la referencia independiente contra la que se verifica el total de Kruskal — con las llamadas de networkx/scipy que usarías en producción anotadas. Cambia entre ellas.

"""Kruskal's algorithm — the same minimum spanning tree Prim builds, by the opposite
strategy. Where Prim grows one tree outward from a seed, Kruskal ignores any starting point
and thinks globally about edges: sort every edge cheapest-first, then walk down that list
adding each edge UNLESS it would connect two nodes that are already connected (which would
form a cycle). Add V−1 safe edges and you have the minimum spanning tree.

Kruskal starts with a FOREST of V separate one-node trees and merges them. Each accepted
edge fuses two trees into one; each rejected edge would have joined a tree to itself. The
one operation it needs — over and over — is "are these two nodes already in the same tree?"
and, if not, "merge their trees." That is precisely the union-find (disjoint-set) structure
from the trees tier, and Kruskal is its headline application: this chapter is where union-find
finally earns its near-constant-time find and union.
"""


# region: dsu
class DSU:
    """Disjoint-set union (union-find) with path compression and union by rank — the engine
    that makes Kruskal fast. `find` returns a canonical representative of a node's set;
    `union` merges two sets. Both run in near-constant amortized time (inverse Ackermann),
    so the union-find work across all of Kruskal is effectively linear."""

    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:            # path compression: point everyone at the root
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        """Merge the sets of a and b. Returns False if they were already the same set (so the
        edge would make a cycle), True if a real merge happened."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                         # already connected → adding this edge cycles
        if self.rank[ra] < self.rank[rb]:        # hang the shorter tree under the taller
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
# endregion


# region: kruskal
def kruskal(edges, n):
    """Minimum spanning tree by Kruskal's method. `edges` is a list of (u, v, w). Sort all
    edges ascending by weight; for each, add it iff its endpoints are in different components
    (union succeeds). Stop once V−1 edges are chosen. O(E log E) — dominated by the sort;
    the union-find work is effectively linear. Returns (mst_edges, total_weight)."""
    dsu = DSU(n)
    mst_edges = []
    total = 0
    for w, u, v in sorted((w, u, v) for u, v, w in edges):
        if dsu.union(u, v):                      # different trees → safe to add, merges them
            mst_edges.append((u, v, w))
            total += w
            if len(mst_edges) == n - 1:          # a spanning tree is complete at V−1 edges
                break
    return mst_edges, total
# endregion

"""The library counterpart, the independent reference, and the rival. In production a
minimum spanning tree comes from networkx or scipy — networkx's default is actually Kruskal:

    import networkx as nx
    T = nx.minimum_spanning_tree(G, weight="weight", algorithm="kruskal")

The reference/rival that makes Kruskal legible is PRIM (last chapter) — the other MST
algorithm, which grows one tree from a seed using a priority queue instead of sorting edges
and merging a forest. They pick possibly-different trees but always the same total weight,
so Prim is the ground truth for Kruskal's total, and the trace generator times both to show
which wins at which density.
"""
import heapq


# region: prim
def prim(adj, n, start=0):
    """Prim's MST from the last chapter: grow one tree, always adding the cheapest edge that
    crosses from the tree to the outside, via a min-heap keyed on edge weight. O(E log V).
    Independent of Kruskal's sort-and-merge approach, so it's the reference for the total."""
    in_tree = [False] * n
    in_tree[start] = True
    total, count = 0, 0
    pq = [(w, v) for v, w in adj[start]]
    heapq.heapify(pq)
    while pq and count < n - 1:
        w, v = heapq.heappop(pq)
        if in_tree[v]:
            continue
        in_tree[v] = True
        total += w
        count += 1
        for c, wc in adj[v]:
            if not in_tree[c]:
                heapq.heappush(pq, (wc, c))
    return total
# endregion

Desde cero vs librería

Kruskal es un reencuentro muy satisfactorio de dos hilos de este libro: la lógica greedy de la propiedad del corte que comparte con Prim, y la estructura union-find del tier de árboles, encontrándose en un algoritmo donde cada una hace funcionar a la otra. Esa es la verdadera lección aquí — no "Kruskal contra Prim" (son casi idénticos en velocidad y llegan al mismo árbol) sino cómo un algoritmo clásico es una composición de una estrategia y una estructura de datos, y cómo la calidad de la estructura decide el costo del algoritmo. La pasada de union-find de 2 milisegundos sobre un cuarto de millón de aristas es toda la justificación de haberle dedicado un capítulo a los conjuntos disjuntos: sin compresión de caminos y unión por rango, esa pasada sería el cuello de botella; con ellas, desaparece y solo queda el sort. En producción llamarías a networkx.minimum_spanning_tree (que usa Kruskal por default) o a la versión compilada de scipy; construirlo tú mismo es lo que convierte "union-find es casi constante" de una cota memorizada en un número que ya mediste, y lo que vuelve razonada la elección entre Kruskal y Prim — lista de aristas y disperso o pre-ordenado, ve por Kruskal; adyacencia y denso, ve por Prim.

Dónde te lo vas a encontrar

Kruskal comparte el espacio de aplicaciones de Prim —diseño de redes de costo mínimo para redes eléctricas, telecom, tuberías, cableado y trazado de circuitos— y agrega algunas propias. Es el método estándar detrás del clustering jerárquico single-linkage: construye el MST y sus aristas, cortadas en orden decreciente, son exactamente el historial de fusión de clusters de los datos. Los algoritmos de segmentación de imágenes (Felzenszwalb-Huttenlocher) son fusión de regiones al estilo Kruskal. Alimenta algoritmos de aproximación para el problema del agente viajero. Genera laberintos perfectos (un MST con pesos aleatorios sobre un grafo de cuadrícula). Su primo paralelo, el algoritmo de Borůvka, que fusiona repetidamente cada componente con su arista saliente más barata de un jalón, impulsa el cómputo distribuido de MST en grafos masivos. Y por lo transparente que es, Kruskal es el algoritmo de MST al que más se recurre cuando la corrección y la claridad importan más que exprimir el último factor constante.

Puntos clave

El algoritmo de Kruskal construye un árbol de expansión mínima ordenando todas las aristas de más barata a más cara y agregando cada una que une dos árboles distintos —detectando ciclos con union-find— en $O(E \log E)$, dominado por completo por el sort. Llega al mismo árbol que Prim, desde la dirección opuesta: fusionando un bosque en lugar de hacer crecer un árbol, con su corrección apoyada en la misma propiedad del corte. Su motor union-find es lo que lo hace rápido, y medir ese motor —un cuarto de millón de fusiones en menos de dos milisegundos— es el premio más claro posible del capítulo de conjuntos disjuntos del tier de árboles. Kruskal y Prim son las dos caras de los árboles de expansión mínima, y cuál elijas depende de la representación de aristas y del contexto, nunca de cuál encuentra un árbol más barato.

Con esto cerramos los algoritmos constructivos sobre grafos. El capítulo final del tier regresa al análisis de la estructura de un grafo dirigido: sus componentes fuertemente conexos — los grupos máximos de nodos que pueden alcanzarse todos entre sí. Encontrarlos es una preciosa búsqueda en profundidad de dos pasadas (el algoritmo de Kosaraju) o una sola muy ingeniosa (el de Tarjan), y cierra el tier de grafos amarrándolo de vuelta con la búsqueda en profundidad donde empezó.