Calculadora Algoritmo de Kruskal

Pseudocódigo

Ordena todas las aristas por peso y luego recorre la lista añadiendo cualquier arista que una dos componentes distintas. Union-Find hace que la comprobación de "componentes distintas" resulte casi gratuita.

Kruskal(grafo):
    ordenar todas las aristas por peso ascendente
    hacerConjunto(v) para cada vértice v
    mst = []

    para cada arista (u, v, w) en orden:
        si buscar(u) != buscar(v):    // componentes distintas
            unir(u, v)
            mst.añadir((u, v, w))
            si mst tiene V - 1 aristas: salir

    devolver mst

Kruskal hace crecer un bosque, no un árbol. Varios fragmentos desconectados se desarrollan de forma independiente y se fusionan a medida que aristas baratas los unen, que es la diferencia estructural con Prim y la razón de que Kruskal maneje grafos desconectados sin esfuerzo: simplemente devuelve un bosque de expansión mínimo. La corrección se sigue de la propiedad del corte aplicada a las fronteras entre componentes, exactamente igual que con Prim.

Ejemplo resuelto, paso a paso

Construye el árbol de expansión mínimo sobre el mismo grafo usado en el ejemplo de Prim, para poder comparar los dos órdenes de descubrimiento.

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

1. Ordenar las aristas. Por peso: B-C con 1, A-B con 2, A-C con 3, C-D con 4, B-D con 7. Cada vértice empieza en su propio conjunto unitario.
2. Aceptar B-C (1). B y C están en conjuntos distintos, así que la arista se acepta y ambos se fusionan. Las componentes son ahora {B, C}, {A} y {D}.
3. Aceptar A-B (2). A y B siguen en conjuntos distintos, así que se acepta y se fusionan. Las componentes son ahora {A, B, C} y {D}.
4. Rechazar A-C (3). A y C están ya en el mismo conjunto, así que esta arista cerraría un ciclo y se omite. Esta es la diferencia visible con Prim, que ni siquiera llegó a considerar A-C una vez que ambos extremos estaban en el árbol.
5. Aceptar C-D (4). C y D están en conjuntos distintos, así que se acepta y se fusionan. Los cuatro vértices forman ya una sola componente y el árbol tiene tres aristas, de modo que el algoritmo puede parar sin examinar B-D con 7.

El árbol de expansión mínimo es B-C, A-B y C-D con peso total 1 + 2 + 4 = 7, idéntico al que produjo Prim desde A. Los árboles coinciden, como debe ocurrir cuando los pesos son distintos, pero el orden de descubrimiento difiere: Prim fue A-B, B-C, C-D creciendo hacia afuera desde A, mientras que Kruskal fue B-C, A-B, C-D en puro orden de peso y tuvo que rechazar explícitamente una arista que cerraba ciclo por el camino.

Complejidad y de dónde sale

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

Ordenar las aristas domina todo lo demás con O(E log E), que equivale a O(E log V) ya que E es a lo sumo V al cuadrado y por tanto log E queda dentro de un factor constante de log V. Tras la ordenación, el bucle realiza a lo sumo 2E operaciones de búsqueda y V - 1 uniones. Con compresión de caminos y unión por rango, cada una cuesta la función inversa de Ackermann de V, que está por debajo de 5 para cualquier entrada que quepa en memoria y se trata como constante. Así que la parte de Union-Find es efectivamente O(E) y la ordenación es todo el coste. Cuando las aristas llegan ya ordenadas, o pueden repartirse en cubetas porque los pesos son enteros pequeños, Kruskal baja a casi lineal y supera claramente a Prim.

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

Kruskal y Prim resuelven el mismo problema. La densidad, el orden de las aristas y la conectividad deciden cuál es mejor.

Errores frecuentes

• Usar Union-Find sin compresión de caminos ni unión por rango. Una implementación ingenua degenera en listas enlazadas y cada búsqueda pasa a costar O(V), llevando el bucle a O(E·V). Ambas optimizaciones son unas pocas líneas cada una y son lo que hace real la cota casi constante.
• Comparar vértices en lugar de representantes de conjunto. La comprobación de ciclo es buscar(u) != buscar(v), no u != v. Comparar los vértices en sí acepta todas las aristas y produce un grafo lleno de ciclos en lugar de un árbol.
• Olvidar parar en V - 1 aristas. No es un fallo de corrección sino un coste innecesario: una vez que el árbol tiene V - 1 aristas ya está completo y toda arista restante será rechazada. En un grafo denso eso supone una gran cantidad de recorrido desperdiciado.
• Suponer una respuesta única con pesos empatados. Cuando varias aristas comparten peso, el orden de la ordenación decide cuáles se toman y distintas implementaciones producen árboles distintos de igual peso total. Comprueba el total, no el conjunto de aristas.
• Aplicarlo a grafos dirigidos. Igual que Prim, Kruskal está definido para grafos no dirigidos. El análogo dirigido es la arborescencia de expansión mínima y requiere el algoritmo de Chu-Liu/Edmonds.

Preguntas frecuentes

¿Cómo funciona el algoritmo de Kruskal?

Ordena todas las aristas por peso y recorre la lista ordenada, añadiendo una arista siempre que sus dos extremos estén en componentes distintas y omitiéndola cuando ya están conectados. Una estructura Union-Find responde a la pregunta de conectividad en tiempo casi constante. El resultado tras V - 1 aristas aceptadas es un árbol de expansión mínimo.

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

O(E log E) en tiempo, dominado por completo por la ordenación de las aristas. Las operaciones de Union-Find solo añaden O(E·α(V)), donde α es la función inversa de Ackermann y es efectivamente constante. Si las aristas ya vienen ordenadas o pueden ordenarse por cubetas, el algoritmo pasa a ser casi lineal.

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

Kruskal considera las aristas globalmente por orden de peso y hace crecer un bosque que se fusiona en un árbol, usando Union-Find para rechazar ciclos. Prim hace crecer un único árbol conectado hacia afuera desde un vértice inicial usando una cola de prioridad. Kruskal encaja con grafos dispersos o con aristas preordenadas y maneja de forma natural entradas desconectadas; Prim encaja con grafos densos.

¿Por qué Kruskal necesita Union-Find?

Porque lo único que pregunta de cada arista es si sus extremos ya están conectados, y esa pregunta se hace E veces. Union-Find la responde en tiempo casi constante con compresión de caminos y unión por rango. Recalcular la conectividad con un recorrido para cada arista costaría O(E·V) en su lugar.

¿Puede Kruskal manejar un grafo desconectado?

Sí, sin cambios. Simplemente devuelve un bosque de expansión mínimo, un árbol por componente conexa, porque durante su ejecución nunca exige que las aristas aceptadas formen una única estructura conectada. Prim, en cambio, se detiene en cuanto agota la componente que contiene su vértice de partida.