Algoritmo de Kruskal
Ordena las aristas, toma la más corta, nunca cierres un ciclo. El algoritmo de Kruskal es quizá el algoritmo voraz más sencillo que existe, y aun así siempre encuentra la forma más barata de conectar todos los nodos de un grafo.
La idea
Un árbol de expansión mínima conecta todos los nodos de un grafo ponderado con la menor longitud total de aristas posible. El algoritmo de Kruskal no hace crecer un solo árbol desde un origen. Mira todo el grafo a la vez, empieza con cada nodo como un trozo por sí solo y va uniendo trozos con la arista más corta disponible hasta que solo queda uno.
Paso a paso
Ordena las aristas de la más corta a la más larga. Pruébalas en ese orden. Si los dos extremos de una arista están en trozos distintos, añádela al árbol: los dos trozos pasan a ser uno. Si los dos extremos ya están en el mismo trozo, la arista cerraría un ciclo, así que se salta. Con n nodos, el árbol está completo tras n − 1 aristas, y no hace falta mirar las aristas restantes.
Un ejemplo
Toma las aristas A–B de longitud 1, B–C 2, A–C 3, C–D 4 y B–D 5. Kruskal añade A–B, luego B–C, que une C al trozo A–B. Luego viene A–C, pero A y C ya están en el mismo trozo, así que cerraría el ciclo A–B–C y se salta. C–D une D, y ahora los cuatro nodos forman un árbol de tres aristas, con longitud total 7. B–D, la arista más larga, ni siquiera se prueba.
Union-find
La única pregunta difícil que se hace el algoritmo de Kruskal es: ¿están ya estos dos nodos en el mismo trozo? Una estructura union-find la responde. Cada trozo es un pequeño árbol de enlaces que apuntan a un representante. Find sigue los enlaces hasta el representante; union pone un representante debajo del otro. La compresión de caminos, que hace que cada nodo visitado apunte directamente al representante, y la unión por tamaño mantienen los enlaces tan cortos que cada pregunta tarda un tiempo casi constante.
Historia y velocidad
Joseph Kruskal publicó el algoritmo en 1956, en un artículo breve en los Proceedings of the American Mathematical Society. Ordenar las aristas es la parte más lenta, así que el trabajo crece con E log E para E aristas. Si las aristas ya están ordenadas, o sus longitudes son números enteros pequeños, es casi lineal.
Pruébalo
Abre la aplicación y pulsa Paso. Las aristas que quedan por probar aparecen bajo el grafo, de la más corta a la más larga. Cada arista que une dos trozos se vuelve verde; cada arista que cerraría un ciclo se dibuja discontinua en rojo. Mira cómo varios trozos pequeños crecen en distintas partes del grafo y se funden, y fíjate en que las últimas aristas a menudo nunca se prueban.
Preguntas frecuentes
¿Por qué el algoritmo de Kruskal ordena las aristas?
Para que cada arista que añade sea la más corta que todavía une dos trozos. Esa elección voraz siempre es segura por la propiedad del corte, y cada arista saltada es la más larga del ciclo que cerraría, así que nunca hace falta.
¿Qué es una estructura de conjuntos disjuntos?
Otro nombre de union-find: una estructura que guarda una colección de conjuntos separados, aquí los trozos del bosque que crece, y sabe decir rápido a qué conjunto pertenece un elemento y unir dos conjuntos.
¿Funciona el algoritmo de Kruskal en un grafo no conexo?
Sí. Simplemente termina con un árbol para cada trozo conexo del grafo, un bosque de expansión mínima, porque ninguna arista puede unir trozos que no están conectados.
¿Se usa el algoritmo de Kruskal para algo más?
Si se detiene pronto, antes de que se fundan los últimos trozos, agrupa los nodos en clústeres: es el clustering de enlace simple. Si se ejecuta sobre una cuadrícula con longitudes de arista aleatorias, genera un laberinto.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba el algoritmo de Kruskal