Algoritmo de Kruskal
El algoritmo de Kruskal es un algoritmo de la teoria de grafos para encontrar un arbol de recubrimiento minimo en un grafo conexo y ponderado. Un árbol generador mínimo de un grafo ponderado es un árbol generador tal que la suma de los pesos de sus aristas es la mínima posible de entre todos los arboles generadores. 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.
Funciona de la siguiente manera:
1.-Se selecciona la arista con menor valor
2.- Después de las aristas que restan se elige la que tiene menor valor
3.- se va repitiendo el paso N°, recordando que no podemos generar ningun ciclo.
4.- finalizamos cuando ya se hayan recorrido todos los vértices, sin importar el que no se hayan recorrido todas las aristas.
Complejidad del Algoritmo:
m el número de aristas del grafo y n el número de vértices, el algoritmo de Kruskal muestra una complejidad O(m log m) o, equivalentemente, O(m log n), cuando se ejecuta sobre estructuras de datos simples.
Ejemplo paso a paso:
Grafo Original
Los numeros de las aristas indican su peso.
AD y CE son las aristas con m enor peso 5,
por eso son resaltada s.
La siguie nte arista con peso 6, ha sido resaltada utilizando el mismo método.
Las siguientes aristas mas pequeñas son AB y BE,
ambas con peso 7.
Finalmente, el proceso termina con la arista EG de peso 9, y se ha encontrado el árbol de expandido mínimo.
,
No hay comentarios:
Publicar un comentario