Algoritmo del árbol de expansión de Kruskal
El algoritmo de Kruskal para encontrar el árbol de expansión de costo mínimo utiliza el enfoque codicioso. Este algoritmo trata el gráfico como un bosque y cada nodo que tiene como un árbol individual. Un árbol se conecta a otro solo y solo si, tiene el menor costo entre todas las opciones disponibles y no viola las propiedades de MST.
Para comprender el algoritmo de Kruskal, consideremos el siguiente ejemplo:
Paso 1: eliminar todos los bucles y bordes paralelos
Elimine todos los bucles y bordes paralelos del gráfico dado.
En caso de bordes paralelos, mantenga el que tenga el menor costo asociado y elimine todos los demás.
Paso 2: organice todos los bordes en su orden creciente de peso
El siguiente paso es crear un conjunto de bordes y pesos, y organizarlos en un orden ascendente de peso (costo).
Paso 3: agregue el borde que tenga el menor peso
Ahora comenzamos a agregar bordes al gráfico comenzando desde el que tiene el menor peso. Continuaremos comprobando que las propiedades de expansión permanezcan intactas. En caso de que, al agregar un borde, la propiedad del árbol de expansión no se mantenga, entonces consideraremos no incluir el borde en el gráfico.
El menor costo es 2 y los bordes involucrados son B, D y D, T. Los agregamos. Agregarlos no viola las propiedades del árbol de expansión, por lo que continuamos con nuestra próxima selección de bordes.
El siguiente costo es 3 y los bordes asociados son A, C y C, D. Los agregamos de nuevo -
El siguiente costo en la tabla es 4, y observamos que sumarlo creará un circuito en la gráfica. -
Lo ignoramos. En el proceso, ignoraremos / evitaremos todos los bordes que crean un circuito.
Observamos que las aristas con costo 5 y 6 también crean circuitos. Los ignoramos y seguimos adelante.
Ahora nos queda solo un nodo para agregar. Entre las dos aristas de menor costo disponibles 7 y 8, agregaremos la arista con el costo 7.
Al agregar el borde S, A, hemos incluido todos los nodos del gráfico y ahora tenemos un árbol de expansión de costo mínimo.