El algoritmo de Kruskal es un algoritmo eficiente para construir el árbol de expansión mínimo de un gráfico no dirigido conectado ponderado . Además, el algoritmo se usa para encontrar algunas aproximaciones para el problema de Steiner [1] .
El algoritmo fue descrito por Joseph Kraskal en 1956 , este algoritmo es casi el mismo que el algoritmo de Boruvka propuesto por Otakar Boruvka en 1926.
Inicialmente, el conjunto actual de aristas se establece en vacío. Luego, mientras sea posible, se realiza la siguiente operación: de todas las aristas cuya suma al conjunto ya existente no provocará la aparición de un ciclo en el mismo, se selecciona la arista de peso mínimo y se suma al conjunto ya existente. . Cuando no hay más tales bordes, el algoritmo está terminado. Un subgrafo de un grafo dado que contiene todos sus vértices y el conjunto de aristas encontrado es su árbol generador de peso mínimo . Una descripción detallada del algoritmo se puede encontrar en la literatura [2] .
Antes de que comience el algoritmo, es necesario clasificar los bordes por peso, lo que lleva un tiempo O(E × log(E)) . Después de eso, es conveniente almacenar los componentes conectados como un sistema de conjuntos disjuntos . Todas las operaciones en este caso tomarán O(E × α(E, V)) , donde α es la función inversa a la función de Ackermann . Dado que para cualquier problema práctico α(E, V) < 5 , podemos tomarlo como una constante, por lo que el tiempo total de ejecución del algoritmo de Kruskal se puede tomar como O(E * log(E)) .
De hecho, el algoritmo de Kruskal encuentra un árbol de expansión de peso mínimo, ya que es un caso especial del algoritmo de Rado-Edmonds [3] para la matroide gráfica , donde los conjuntos independientes son conjuntos acíclicos de aristas.
| Imagen | Descripción |
|---|---|
| Los bordes AD y CE tienen un peso mínimo de 5. Un borde AD se elige arbitrariamente (resaltado en la figura). Como resultado, obtenemos un conjunto de vértices seleccionados ( A , D ). | |
| Ahora el borde CE tiene el peso más pequeño igual a 5 . Dado que agregar CE no forma un ciclo, lo elegimos como el segundo borde. Dado que este borde no tiene vértices comunes con el conjunto existente de vértices seleccionados ( A , D ), obtenemos el segundo conjunto de vértices seleccionados ( C , E ). | |
| De igual forma, seleccionamos la arista DF , cuyo peso es igual a 6. En este caso no ocurre ningún ciclo, ya que no existen (entre las no seleccionadas) aristas que tengan ambos vértices de una ( A , D , F ) o de la segunda ( C , E ) conjunto de vértices seleccionados . | |
| Los siguientes bordes son AB y BE con peso 7. El borde AB resaltado en la figura se elige al azar. Esto agrega el vértice B al primer conjunto de vértices seleccionados ( A , B , D , F ). La arista BD previamente no seleccionada se resalta en rojo, ya que sus vértices están incluidos en el conjunto de vértices seleccionados ( A , B , D , F ) y, por lo tanto, ya existe un camino (verde) entre B y D (si este se seleccionaron los bordes, luego ciclo ABD ).
El siguiente borde solo se puede seleccionar después de encontrar todos los ciclos. | |
| De manera similar, se selecciona una arista BE con un peso de 7. Dado que esta arista tiene vértices en ambos conjuntos de vértices seleccionados ( A , B , D , F ) y ( C , E ), estos conjuntos se fusionan en uno ( A , B , C , D , E , F ). En esta etapa, muchas más aristas se resaltan en rojo, ya que los conjuntos de vértices seleccionados y, por lo tanto, los conjuntos de aristas seleccionadas se han fusionado. Ahora BC creará un ciclo BCE , DE creará un ciclo DEBA y FE creará un ciclo FEBAD . | |
| El algoritmo finaliza con la adición de una arista EG con peso 9. El número de vértices seleccionados ( A , B , C , D , E , F , G ) = 7 corresponde al número de vértices en el gráfico. Se ha construido el árbol de expansión mínima. |