32. Algoritmo de Kruskal

32.1 Introducción

El algoritmo de Kruskal resuelve el problema del árbol de expansión mínima en grafos no dirigidos, conectados y ponderados. A diferencia de Prim, no comienza desde un vértice ni mantiene necesariamente una única región conectada.

Al principio cada vértice es un árbol independiente. Las aristas más baratas van uniendo esos árboles hasta formar uno solo con todos los vértices.

32.2 Idea fundamental

1. Ordenar todas las aristas por peso creciente.
2. Crear un componente separado para cada vértice.
3. Examinar las aristas en ese orden.
4. Aceptar una arista si conecta componentes diferentes.
5. Detenerse al reunir V − 1 aristas.

32.3 El bosque inicial

Antes de seleccionar conexiones, cada vértice constituye un árbol de un solo nodo. El conjunto completo es un bosque con V componentes.

Cada arista aceptada fusiona exactamente dos componentes, por lo que su cantidad disminuye en uno. Después de V − 1 fusiones queda un único árbol.

32.4 Por qué se evitan los ciclos

Si los extremos de una arista ya pertenecen al mismo componente, existe un camino entre ellos. Agregar otra conexión cerraría un ciclo y no ayudaría a incorporar ningún vértice nuevo.

Si pertenecen a componentes distintas, la arista las une sin crear un ciclo.

32.5 Relación con la propiedad del corte

Cada componente del bosque define un corte entre sus vértices y el resto. La arista examinada de menor peso que conecta dos componentes es segura según la propiedad del corte.

La demostración también puede formularse con un intercambio: si un MST no contiene la arista elegida, podemos agregarla, quitar del ciclo resultante una arista no más barata y conservar el costo óptimo.

32.6 Simulación interactiva paso a paso

Avanza por la lista ordenada. El laboratorio mostrará qué arista se examina, si se acepta o descarta, y cómo cambian los componentes del bosque.

Celeste representa las aristas aceptadas, rosa la arista actual y rojo una conexión descartada por formar un ciclo.

32.7 Ejemplo conceptual

Supongamos que A—B y B—C ya fueron aceptadas. Cuando llega A—C, sus extremos pertenecen al mismo componente {A, B, C}; por tanto, se descarta aunque sea la siguiente arista de la lista.

En cambio, una arista C—D puede unir {A, B, C} con {D} y se acepta. Kruskal toma decisiones usando componentes, no el grado de los vértices ni una ruta desde un origen.

32.8 Union-Find

La estructura de conjuntos disjuntos, también llamada Union-Find o DSU, mantiene los componentes eficientemente mediante dos operaciones:

• find(x): devuelve el representante del conjunto que contiene a x.
• union(a, b): fusiona los conjuntos de a y b.

32.9 Compresión de caminos

Los conjuntos se representan como árboles de padres. Al ejecutar find, la compresión de caminos conecta directamente con la raíz a los nodos recorridos.

find(x) {
  if (this.padre[x] !== x) {
    this.padre[x] = this.find(this.padre[x]);
  }
  return this.padre[x];
}

Las búsquedas posteriores atraviesan menos niveles y se vuelven prácticamente constantes.

32.10 Unión por rango

Al fusionar dos árboles conviene colocar la raíz de menor rango debajo de la de mayor rango. Si ambos rangos son iguales, cualquiera puede ser la nueva raíz y su rango aumenta.

También puede almacenarse el tamaño de cada conjunto y unir siempre el más pequeño al más grande.

32.11 Implementación de Union-Find

class UnionFind {
  constructor(n) {
    this.padre = Array.from({ length: n }, (_, i) => i);
    this.rango = Array(n).fill(0);
  }

  find(x) {
    if (this.padre[x] !== x) {
      this.padre[x] = this.find(this.padre[x]);
    }
    return this.padre[x];
  }

  union(a, b) {
    let raizA = this.find(a);
    let raizB = this.find(b);
    if (raizA === raizB) return false;

    if (this.rango[raizA] < this.rango[raizB]) [raizA, raizB] = [raizB, raizA];
    this.padre[raizB] = raizA;
    if (this.rango[raizA] === this.rango[raizB]) this.rango[raizA]++;
    return true;
  }
}

32.12 Implementación completa de Kruskal

function kruskal(cantidadVertices, aristas) {
  const ordenadas = [...aristas].sort((a, b) => a.peso - b.peso);
  const conjuntos = new UnionFind(cantidadVertices);
  const mst = [];
  let costo = 0;

  for (const arista of ordenadas) {
    if (conjuntos.union(arista.origen, arista.destino)) {
      mst.push(arista);
      costo += arista.peso;
      if (mst.length === cantidadVertices - 1) break;
    }
  }
  return {
    aristas: mst,
    costo,
    completo: mst.length === cantidadVertices - 1
  };
}

32.13 Grafos desconectados

Si el grafo no es conectado, ninguna selección puede producir un árbol que abarque todos los vértices. Kruskal procesa las conexiones disponibles y obtiene un árbol mínimo para cada componente.

El resultado se denomina bosque generador mínimo.

32.14 Empates y unicidad

Cuando varias aristas tienen el mismo peso, pueden examinarse en diferentes órdenes. Es posible obtener árboles distintos, pero todos tendrán el mismo costo mínimo.

Para resultados reproducibles se agrega un criterio secundario, por ejemplo los identificadores de los extremos. Si todos los pesos son distintos, el MST es único.

32.15 Kruskal y Prim

32.16 Complejidad

Ordenar las E aristas cuesta O(E log E). Las operaciones de Union-Find agregan O(E α(V)), donde α es la función inversa de Ackermann y crece extremadamente despacio.

En la práctica, la ordenación domina el tiempo de ejecución.

32.17 Aplicaciones

• Diseño económico de redes de comunicación, caminos y tuberías.
• Agrupamiento jerárquico y segmentación de datos.
• Construcción de redes a partir de una lista de conexiones posibles.
• Obtención de bosques mínimos en grafos desconectados.
• Problemas donde las aristas ya llegan ordenadas por costo.
• Base para algoritmos de aproximación y análisis de conectividad.

32.18 Errores comunes

• Ordenar los pesos como texto en lugar de numéricamente.
• Aceptar una arista sin comprobar si sus extremos ya están conectados.
• Aplicar el algoritmo directamente a un grafo dirigido.
• Modificar la lista original al ordenarla sin que el programa lo espere.
• Olvidar la compresión de caminos o la unión por rango.
• Suponer que siempre se obtendrán V − 1 aristas.
• Confundir costo total mínimo con caminos mínimos entre pares.

32.19 Qué debes recordar de este tema

• Kruskal procesa todas las aristas por peso creciente.
• Construye un bosque que se fusiona progresivamente.
• Acepta una arista solo si conecta componentes diferentes.
• Union-Find permite comprobar y fusionar componentes eficientemente.
• La propiedad del corte justifica cada elección.
• Su complejidad está dominada por O(E log E).
• En grafos desconectados produce un bosque generador mínimo.

32.20 Conclusión

Kruskal transforma una estrategia voraz muy sencilla en un algoritmo eficiente: considerar primero las conexiones baratas y utilizar Union-Find para aceptar únicamente las que unen regiones separadas.

En el próximo tema estudiaremos las redes de flujo, donde las aristas representan capacidades y el objetivo consiste en transportar la mayor cantidad posible desde una fuente hasta un sumidero.