Kruskal (MST)

Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

El problema: conectar todos los lugares al menor costo

Queremos tender cables entre cuatro edificios. Cada conexión posible tiene un precio, y basta que todos puedan comunicarse, quizá pasando por otros. Un árbol de expansión conecta todos los vértices sin ciclos; con V vértices tiene V−1 aristas. Buscamos el de menor suma total de pesos, llamado MST. El grafo de entrada es no dirigido y, para obtener un árbol, debe ser conexo.

Considera A–B con costo 1, B–C con 2, A–C con 3, C–D con 4 y B–D con 5. Kruskal ordena todas las conexiones por costo y acepta una si conecta dos grupos que todavía estaban separados.

12345ABCDMST1 + 2 + 4Costo 7Gruesas: aceptar. Discontinuas: rechazar porque cierran un ciclo.

Si el diagrama no cabe, deslízalo horizontalmente.

Arista, en ordenDecisiónGrupos después de decidirCosto acumulado
A–B, 1aceptar{A,B}, {C}, {D}1
B–C, 2aceptar{A,B,C}, {D}3
A–C, 3rechazar: ya existe el camino A–B–C{A,B,C}, {D}3
C–D, 4aceptar{A,B,C,D}7
B–D, 5rechazar: sus extremos ya están conectados{A,B,C,D}7

El resultado usa tres aristas y cuesta 7. Que una arista sea barata no basta: A–C es más barata que C–D, pero cerraría un ciclo sin alcanzar a D.

Cómo comprobar si una arista cierra un ciclo

Mantenemos los grupos con Union-Find. Cada vértice apunta a un padre, y seguir padres lleva a un representante o raíz. Al principio cada vértice es su propio grupo. find(x) obtiene su raíz y unite(a,b) fusiona dos grupos distintos; devuelve falso si ya eran el mismo.

Una nueva arista cierra un ciclo exactamente cuando sus extremos ya están conectados por las aristas aceptadas. Por eso basta comparar representantes; no necesitamos buscar el camino completo en cada paso. El código incluye esta estructura para poder usar la ficha directamente.

Por qué elegir la más barata es seguro

Imagina que ya aceptamos algunas aristas y elegimos e, la siguiente que une dos grupos distintos. Supongamos que tenemos un árbol óptimo T que contiene todas nuestras elecciones anteriores.

Si e ya pertenece a T, no hay nada que cambiar. Si no, añadirla a T crea un ciclo. Ese ciclo contiene otra arista f que sale del grupo de uno de los extremos de e. Esa f no era una elección previa: las elecciones previas quedan dentro de los grupos actuales.

Como e es la más barata disponible que cruza entre grupos, su peso no supera al de f. Podemos quitar f y conservar e: seguimos teniendo un árbol, de costo no mayor, que respeta todas nuestras elecciones. Este argumento de intercambio permite repetir la decisión hasta conectar todos los vértices.

Implementación y llamada de ejemplo

// Union-Find compacto: compresión de caminos; esta variante no une por tamaño.
struct UnionFind {
    vector<int> p;
    UnionFind(int n) : p(n) { for (int i = 0; i < n; i++) p[i] = i; }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; p[a] = b; return true; }
};
 
// aristas: {peso, u, v}.  Devuelve el costo del MST (grafo conexo).
// edges se recibe por valor a propósito: se ordena una copia y la del llamador queda intacta.
long long kruskal(int n, vector<array<long long,3>> edges) {
    sort(edges.begin(), edges.end());
    UnionFind dsu(n);
    long long cost = 0;
    for (auto& e : edges)
        if (dsu.unite((int)e[1], (int)e[2])) cost += e[0];
    return cost;
}

Numera A…D como 0…3. Crea un vector<array<long long,3>> con {{1,0,1}, {2,1,2}, {3,0,2}, {4,2,3}, {5,1,3}}. Cada triple es {peso, u, v}, en ese orden. kruskal(4, edges) devuelve 7. La lista se copia al entrar: ordenar no modifica la lista del llamador.

La función devuelve el costo, no las aristas elegidas. Para recuperarlas, guarda cada triple cuando unite devuelva verdadero. Todos los extremos deben ser índices válidos y la suma de pesos debe caber en long long.

La implementación compacta comprime caminos, pero no une por tamaño: no es la versión completa de DSU (Union-Find). El costo de ordenar es O(E log(E+1)); una cota conservadora para el conjunto del algoritmo es O((V+E) log(V+E+1)). Usa O(V+E) memoria adicional, incluida la copia de las aristas. Para entradas adversas grandes, conviene usar la versión de DSU con unión por tamaño, que también evita árboles de padres muy profundos antes de comprimirlos.

Límites que importan

Con pesos negativos, cero o empates, el mismo argumento funciona: Kruskal no presupone pesos positivos. Con empates puede haber varios árboles óptimos. Los lazos se rechazan y las aristas paralelas no requieren un tratamiento especial.

Si el grafo no es conexo, la función devuelve el costo de un bosque de expansión mínima: un árbol por componente. No informa por sí sola del fallo de conectividad; para exigir un MST, cuenta que se acepten exactamente V−1 aristas cuando V > 0. Un solo vértice requiere cero aristas y cuesta cero.

Otra forma de construir un MST es Prim (MST).