ALGORITMO DE KRUSKAL

ALGORITMO DE KRUSKAL

Es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo.

El algoritmo se basa en una propiedad clave de los árboles que permite estar seguros de si un arco debe pertenecer al árbol o no, y usar esta propiedad para seleccionar cada arco.

PASOS

1.    Se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado

2.    Se crea un conjunto C que contenga a todas las aristas del grafo

·         mientras C es no vacío

1.    eliminar una arista de peso mínimo de C

2.    si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol

3.    en caso contrario, se desecha la arista

Las limitaciones que se presentan con el problema de la implementación del algoritmo de Kruskal es la creación de un algoritmo adicional que nos compruebe que al adicionar una arista al grafo no nos haga un ciclo.

EJEMPLO: