¿Qué es el algoritmo de Krushal?

El algoritmo de Krushal ayuda a encontrar el árbol de expansión mínimo para un gráfico ponderado conectado.

Encuentra el subconjunto de aristas que pueden atravesar cada vértice de la gráfica. Este algoritmo encuentra una solución óptima en cada etapa en lugar de encontrar un óptimo global.

Los pasos de los algoritmos son los siguientes.

Paso 1- Crea un bosque. Cada gráfica del bosque es un árbol separado. Un bosque es una colección de árboles separados. Podemos obtenerlo eliminando el nodo raíz y los bordes que conectan los nodos raíz al nodo de primer nivel.

Paso 2- Crea una cola de prioridad que consista en todos los bordes del gráfico.

Paso 3: repita los pasos 4 y 5, si la cola de prioridad no está vacía.

Paso 4 - Eliminar un borde de la cola de prioridad.

Paso 5: si el borde resultante del paso 4 conecta dos árboles, agrégalo al bosque; Si no se desecha el borde.

(0 votes)