El algoritmo de Kruskal explicado

Mohammed Islam Hadjoudj

Ingeniero experto en investigación de operaciones

1. Introducción al algoritmo de Kruskal

El algoritmo de Kruskal construye un árbol de expansión mínima: a partir de un grafo conexo, no dirigido y ponderado, selecciona el conjunto de aristas más barato que toca todos los vértices sin formar ningún ciclo. Para V vértices, ese conjunto contiene siempre exactamente V - 1 aristas.

Mientras que el algoritmo de Prim hace crecer un único árbol conexo hacia fuera desde un vértice inicial, el de Kruskal ignora la conectividad casi por completo hasta el final. Ordena todas las aristas del grafo por peso, recorre esa lista de la más barata a la más cara y conserva cada arista salvo que al hacerlo cerrara un ciclo. No consulta nada más. No hay vértice de partida ni noción de frontera.

La consecuencia es que Kruskal pasa la mayor parte de su ejecución sosteniendo un bosque en lugar de un árbol: muchos fragmentos pequeños repartidos por el grafo, que crecen y se fusionan de forma independiente y que solo se funden en un único árbol de expansión con la última arista que acepta. Esa diferencia de forma es lo que le hace comportarse de otro modo en grafos dispersos, con entrada inconexa y bajo un perfilador.

2. Por qué funciona: la propiedad del ciclo

La corrección de Prim descansa sobre un teorema acerca de qué aristas es seguro aceptar. Kruskal dedica otro tanto de su tiempo a rechazar aristas, así que conviene enunciar el teorema complementario que justifica descartar una.

La demostración refleja la de la propiedad del corte. Supongamos que la arista más pesada e de cierto ciclo sí perteneciera a un árbol de expansión mínima T. Quitar e de T lo parte en dos componentes. El resto de ese ciclo sigue discurriendo entre esas dos componentes, así que alguna otra arista del ciclo f las vuelve a conectar. Coloca f en su lugar. Tienes de nuevo un árbol de expansión y, como e era estrictamente la más pesada, el nuevo árbol es estrictamente más ligero, lo que contradice que T fuera mínimo.

Fíjate ahora en lo que ocurre cuando Kruskal rechaza una arista. Llega a la arista e y descubre que ambos extremos ya están en el mismo fragmento. Eso significa que ya existe un camino entre ellos, construido enteramente con aristas que el algoritmo aceptó antes, es decir, con aristas no más pesadas que e. Añadir e cerraría un ciclo en el que e es el miembro más pesado. Por la propiedad del ciclo, descartarla no cuesta nada.

Las aristas aceptadas son seguras por la misma razón que las de Prim. Cuando una arista une dos fragmentos distintos, es la arista restante más barata que cruza el corte que separa un fragmento de todo lo demás, así que la propiedad del corte se aplica sin cambios. Kruskal es voraz en ambas direcciones a la vez, y ambas direcciones son teoremas.

3. Cómo se fusiona el bosque

En concreto, el algoritmo empieza con cada vértice en su propio fragmento: V fragmentos, cero aristas. Al procesar la lista ordenada de aristas, plantea una sola pregunta a cada arista (u, v):

• ¿Están u y v ya en el mismo fragmento? Entonces la arista cerraría un ciclo. Descártala y sigue.
• ¿Están en fragmentos distintos? Entonces acepta la arista y fusiona los dos fragmentos en uno.

Cada arista aceptada reduce el número de fragmentos en exactamente uno. Partir de V fragmentos y terminar en uno significa exactamente V - 1 aceptaciones, que es la condición de parada. Una vez alcanzadas, se garantiza que toda arista restante de la lista será rechazada, de modo que el bucle puede salir antes.

Todo el algoritmo se reduce por tanto a una única cuestión de estructuras de datos: ¿cómo compruebas "¿mismo fragmento?" y "fusiona estos dos fragmentos" con rapidez, millones de veces? Eso es exactamente lo que proporciona union-find.

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

Ordenarlas por peso da el orden que el algoritmo recorrerá en realidad:

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

Cada vértice empieza solo, así que el bosque comienza como {A} {B} {C} {D} {E} {F}.

1. A-C (1). Aceptar. Fragmentos distintos. El bosque pasa a {AC} {B} {D} {E} {F}. Total acumulado 1.
2. B-C (2). Aceptar. B está solo, C está con A. El bosque pasa a {ABC} {D} {E} {F}. Total 3.
3. D-E (2). Aceptar. Observa que esto construye un fragmento lejos del primero. El bosque pasa a {ABC} {DE} {F}. Total 5.
4. E-F (3). Aceptar. El bosque pasa a {ABC} {DEF}. Total 8.
5. A-B (4). Rechazar. A y B ya están ambos en {ABC}, así que esto cerraría el ciclo A-C-B-A. Descartada.
6. B-D (5). Aceptar. Esta arista tiende un puente entre los dos fragmentos restantes. El bosque pasa a {ABCDEF}. Total 13.

Cinco aristas aceptadas para seis vértices, así que el algoritmo se detiene sin llegar a examinar C-D (6), C-E (7) ni D-F (8). El árbol resultante es A-C (1), B-C (2), D-E (2), E-F (3), B-D (5), con peso total 13, exactamente el árbol que Prim encuentra en el mismo grafo.

El paso 3 es el momento que distingue a este algoritmo. Prim no habría podido tomar D-E en ese punto, porque ninguno de sus extremos tocaba su árbol en crecimiento. A Kruskal no le importa: inicia sin reparos un segundo fragmento, sin relación con el primero, al otro lado del grafo, y ya se preocupará después de conectarlos. Y el paso 5 muestra la propiedad del ciclo en acción, rechazando justo la arista que es la más pesada del ciclo que habría creado.

5. Union-find: la estructura que lo hace rápido

La forma ingenua de comprobar si dos vértices ya están conectados es lanzar un recorrido desde uno y ver si alcanzas el otro. Eso cuesta O(V) por arista y arrastra todo el algoritmo a O(V * E), peor que la ordenación a la que se suponía que complementaba.

Union-find, también llamada estructura de conjuntos disjuntos, responde a ambas preguntas en tiempo casi constante. Mantiene cada fragmento como un árbol de punteros al padre con un elemento representante en la raíz, y expone dos operaciones:

• find(x) devuelve el representante del fragmento de x. Dos vértices están en el mismo fragmento exactamente cuando sus representantes son idénticos.
• union(x, y) fusiona los dos fragmentos colgando una raíz por debajo de la otra.

Dos optimizaciones la hacen lo bastante rápida como para desaparecer del análisis de complejidad. La unión por rango cuelga siempre el árbol más bajo bajo el más alto, evitando que la estructura degenere en una cadena. La compresión de caminos reapunta directamente a la raíz cada nodo visitado durante un find, de modo que las consultas repetidas se abaratan a medida que el algoritmo avanza.

Con ambas aplicadas, una secuencia de m operaciones sobre n elementos cuesta O(m α(n)), donde α es la función inversa de Ackermann. Crece tan despacio que se mantiene por debajo de 5 para cualquier entrada que quepa en el universo observable, así que el trabajo de union-find en Kruskal es efectivamente lineal en el número de aristas.

6. Implementación y pseudocódigo

Como union-find carga con la dificultad, el algoritmo en sí es breve.

function Kruskal(V, edges):
    ordena edges por peso, ascendente
    makeSet(v) para cada vértice v     // V fragmentos unitarios
    mst = []

    for cada arista (u, v, w) en orden:
        if find(u) != find(v):         // fragmentos distintos
            union(u, v)
            mst.append((u, v, w))
            if size(mst) == V - 1:     // salida temprana: árbol completo
                break

    return mst

Dos detalles merecen defensa. El break no es necesario para la corrección, ya que toda arista posterior sería rechazada de todos modos, pero en un grafo denso se salta la mayor parte de la lista. Y quitarlo por completo no es un error: es lo que convierte esto en un algoritmo de bosque de expansión mínima, como se explica más abajo.

La comparación find(u) != find(v) es el único lugar donde se consideran los ciclos. No hay detección explícita de ciclos en ninguna parte, y ahí reside la elegancia del enfoque: la contabilidad de la conectividad hace ese trabajo de forma implícita.

7. Complejidad temporal y espacial

• Ordenación: O(E log E). Esto domina todo lo demás. Como E < V2, se cumple log E < 2 log V, así que la cota se escribe de forma equivalente como O(E log V).
• Union-find: O(E α(V)). Como mucho dos llamadas a find y una a union por arista. Efectivamente lineal.
• En total: O(E log E). La ordenación y nada más.
• Espacio: O(V + E). Los arreglos de padre y rango son O(V); la propia lista de aristas es O(E).

Como el coste se concentra en un solo punto, todas las optimizaciones útiles atacan la ordenación. Si las aristas llegan ya ordenadas, o los pesos son enteros pequeños que permiten un radix sort o counting sort, todo el algoritmo baja a O(E α(V)), muy cerca de lineal. Una ordenación parcial o un montículo perezoso también ayudan: rara vez necesitas el orden completo, porque el algoritmo suele detenerse mucho antes de llegar a las aristas más pesadas.

8. Kruskal frente a Prim

Ambos son voraces, ambos se justifican con el mismo par de teoremas y, en un grafo con pesos distintos, ambos devuelven el mismo árbol. Las diferencias prácticas se derivan de qué mantiene conectado cada uno.

                 Kruskal                      Prim
estructura       bosque de fragmentos         un arbol en crecimiento
guiado por       lista de aristas ordenada    cola de prioridad
necesita         union-find                   monticulo (o barrido V x V)
coste            O(E log E)                   O(E log V), denso O(V^2)
mejor en         grafos dispersos             grafos densos
inconexo         da un bosque de expansion    solo abarca una componente

La regla práctica es la densidad. En un grafo disperso, E es pequeño, la ordenación sale barata y gana Kruskal. En un grafo denso, donde E se acerca a V2, ordenar unas V2 aristas cuesta O(V2 log V), mientras que Prim con matriz de adyacencia corre en un plano O(V2) y toma la delantera.

9. Notas prácticas y errores frecuentes

Bosques de expansión y grafos inconexos

Aquí Kruskal tiene una ventaja estructural genuina. Ejecútalo sobre un grafo que no sea conexo y sencillamente nunca alcanzará V - 1 aristas aceptadas. Agota la lista de aristas, y lo que queda es un bosque de expansión mínima: el árbol de expansión mínima de cada componente conexa, calculado en una sola pasada y sin tratamiento especial.

Prim no puede hacer esto desde un único inicio. Lanzado en un vértice, abarca la componente de ese vértice y se detiene, devolviendo en silencio un árbol que parece válido pero que cubre solo parte del grafo. Recuperar el resto exige detectar el déficit y reiniciar desde un vértice no visitado, una vez por componente. El recuento es además el diagnóstico: si Kruskal termina habiendo aceptado V - 1 aristas, el grafo era conexo; si aceptó V - k, el grafo tenía k componentes.

Árbol de expansión máxima

Ordena de forma descendente en lugar de ascendente y cada línea del algoritmo sigue siendo válida. La propiedad del ciclo se convierte en un argumento de propiedad del corte sobre pesos negados, y obtienes el árbol de expansión más pesado. Negar los pesos y ejecutar el algoritmo sin cambios funciona igual de bien.

Reverse-delete

La imagen especular de Kruskal: ordena las aristas de la más pesada a la más ligera y elimina cada una salvo que eliminarla desconecte el grafo. Se justifica con la misma propiedad del ciclo leída al revés, y produce el mismo árbol. Rara vez se usa porque la comprobación de conectividad tras cada eliminación es mucho más cara que una consulta a union-find.

Pesos empatados

Cuando varias 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 ordene tu algoritmo de ordenación los empates. El ejemplo de arriba contiene uno: B-C y D-E pesan ambas 2. Todos los árboles resultantes son igual de óptimos, así que cualquier prueba que compare contra una lista fija de aristas es frágil. Compara el peso total en su lugar.

Bucles y aristas paralelas

Un bucle siempre falla la comprobación find(u) != find(v) y se descarta automáticamente, así que no necesita tratamiento especial. Entre aristas paralelas, la más barata se alcanza primero y se acepta, y las demás se rechazan luego como ciclos. Kruskal es inusualmente indulgente con las entradas desordenadas.

10. Aplicaciones en el mundo real

Diseño de redes e infraestructuras

La motivación original: conectar un conjunto fijo de emplazamientos con la menor cantidad total de cable, tubería o vía. La visión centrada en aristas de Kruskal encaja de forma natural cuando la entrada ya llega como una lista de enlaces candidatos con sus costes, que es como suelen presentarse esos datos.

Agrupamiento jerárquico

Ejecuta Kruskal y registra el orden en que se fusionan los fragmentos: habrás realizado un agrupamiento aglomerativo de enlace simple. La secuencia de fusiones es precisamente el dendrograma, y detenerse antes, en V - k aristas, deja exactamente k grupos. Esta equivalencia explica por qué los árboles de expansión mínima aparecen tan a menudo en aprendizaje no supervisado.

Segmentación de imágenes

Tratando los píxeles como vértices y las diferencias de intensidad como pesos de arista, el algoritmo de segmentación de Felzenszwalb y Huttenlocher es en esencia Kruskal con un predicado de fusión que compara la variación interna del fragmento con el peso de la arista.

Diseño de circuitos y trazado

Minimizar la longitud total de pista entre contactos fijos es un problema de árbol de expansión mínima, y la lista de aristas de rutas candidatas es justo lo que un enrutador ya tiene a mano.

11. Recursos académicos e historia

A diferencia del algoritmo de Prim, que se descubrió de forma independiente al menos tres veces, este tiene una atribución limpia.

• Joseph B. Kruskal (1956) lo publicó en una nota de tres páginas, On the shortest spanning subtree of a graph and the traveling salesman problem, en los Proceedings of the American Mathematical Society. El artículo apareció un año antes que el de Prim y treinta años después que el de Borůvka.
• Otakar Borůvka (1926) había planteado y resuelto el problema del árbol de expansión mínima décadas antes, mientras planificaba la electrificación de la Moravia rural.
• Robert Tarjan (1975) demostró la cota amortizada casi constante para union-find con unión por rango y compresión de caminos, que es lo que fija en O(E α(V)) la parte no dedicada a ordenar del coste de Kruskal.

Para la historia completa de la atribución del problema, consulta a Graham y Hell. Para demostraciones rigurosas de las propiedades del corte y del ciclo 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. Las citas completas figuran al final de este artículo.