in

Algoritmo del árbol de expansión de Kruskal

mst graph

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:

Gráfico MST

Paso 1: eliminar todos los bucles y bordes paralelos

Elimine todos los bucles y bordes paralelos del gráfico dado.

Gráfico MST con bucles

En caso de bordes paralelos, mantenga el que tenga el menor costo asociado y elimine todos los demás.

Gráfico MST sin bucles

Paso 2: organice todos los bordes en su orden creciente de peso

El siguiente paso es crear un conjunto de bordes y peso, y organizarlos en un orden ascendente de peso (costo).

Pesaje ascendente MST

Paso 3: agregue el borde que tenga el menor peso

Ahora comenzamos a agregar bordes al gráfico comenzando por 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.

Paso uno de MST Graph

El menor costo es 2 y los bordes involucrados son B, D y D, T. Los sumamos. 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 –

Paso dos de MST Graph

El siguiente costo en la tabla es 4, y observamos que sumarlo creará un circuito en la gráfica. –

Paso tres de MST Graph

Lo ignoramos. En el proceso ignoraremos / evitaremos todos los bordes que crean un circuito.

Paso cuatro de MST Graph

Observamos que las aristas con costo 5 y 6 también crean circuitos. Los ignoramos y seguimos adelante.

Paso cinco de MST Graph

Ahora nos queda solo un nodo para agregar. Entre los dos bordes de menor costo disponibles 7 y 8, agregaremos el borde con el costo 7.

Algoritmo MST Kruskals

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.

spanning_tree.htm

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

ataques prediccion tcp

que es y como nos puede afectar

apple touch icon@2

jquery – ¿Verificando que algo está vacío en Javascript?