Kruskal y Prim

Conectar un conjunto de puntos —ciudades, nodos de una red, componentes de un circuito— gastando lo menos posible en enlaces. La respuesta es un árbol generador mínimo, y hay dos formas clásicas de construirlo, las dos golosas y las dos correctas por la misma razón de fondo.

Conectar todo con el menor peso total

Dado un grafo no dirigido, conexo y con pesos, se busca el subconjunto de aristas que conecte todos los vértices con peso total mínimo. Ese subconjunto no puede tener ciclos: sacar una arista de un ciclo mantiene la conexión y baja el costo.

Un árbol sobre $V$ vértices tiene exactamente $V-1$ aristas. El problema es elegir cuáles, y hacerlo bien entre una cantidad astronómica de árboles posibles.

La propiedad del corte, que justifica a los dos

Lo que justifica a los dos algoritmos es la propiedad del corte. Si se parte el conjunto de vértices en dos, la arista más liviana que cruza esa división pertenece a algún árbol generador mínimo.

La demostración es un intercambio: si un árbol óptimo no la incluye, agregarla forma un ciclo que necesariamente cruza la división por otra arista más pesada; cambiarla por la liviana da un árbol igual de válido y no más caro. Kruskal y Prim son dos maneras de elegir el corte.

Kruskal: ordenar aristas y evitar ciclos

Kruskal ordena todas las aristas por peso creciente y las va tomando, salteando las que conectarían dos vértices del mismo grupo —que formarían ciclo—. Termina con $V-1$ aristas.

La pregunta “¿ya están conectados?” es exactamente lo que responde union-find. Ordenar domina el costo: $O(E\log E)$, y las consultas de conjuntos disjuntos son prácticamente constantes. Durante la ejecución hay varios fragmentos sueltos que recién al final se unen en un árbol.

Prim: hacer crecer un solo árbol

Prim arranca de un vértice cualquiera y hace crecer un único árbol: en cada paso agrega la arista más liviana que conecta el árbol con un vértice de afuera.

La estructura que hace falta es una cola de prioridad con los vértices pendientes, ordenados por el costo de engancharlos. El costo es $O((V+E)\log V)$, y el parecido con Dijkstra es más que superficial: la única diferencia es qué se guarda en la cola —el peso de la arista de conexión, no la distancia acumulada desde el origen—.

Cuál conviene según la densidad

En grafos ralos suele convenir Kruskal, sobre todo si las aristas ya vienen ordenadas o se pueden ordenar barato: ahí el algoritmo es casi lineal. En grafos densos conviene Prim, que no necesita mirar todas las aristas de entrada y con una implementación matricial da $O(V^2)$.

Hay un detalle sobre la unicidad: si todos los pesos son distintos, el árbol generador mínimo es único y los dos algoritmos devuelven el mismo. Con pesos repetidos pueden dar árboles distintos, ambos óptimos.

Dónde aparece, además del tendido de redes

Más allá del tendido de redes, el árbol generador mínimo aparece en clustering: sacarle las $k-1$ aristas más pesadas parte los datos en $k$ grupos separados, que es el clustering de enlace simple.

También sirve como cota inferior en branch and bound para el viajante de comercio. Y una advertencia importante: conectar todo al mínimo costo no es lo mismo que minimizar la distancia entre dos puntos. El camino entre dos vértices dentro del árbol puede ser mucho peor que el camino mínimo del grafo.

Cuál de los dos, y para qué sirve un árbol generador

Cierre

Kruskal ordena aristas y evita ciclos con union-find; Prim hace crecer un árbol con una cola de prioridad. Los dos son golosos y correctos por la propiedad del corte: la arista más liviana que cruza una división siempre entra en algún óptimo.