El Algoritmo
de Kruskal es un algoritmo de la teoría de gráficos para encontrar un árbol recubridor
mínimo en un gráfico 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. Si el gráfico
no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido
mínimo para cada componente conexa).
El algoritmo de Kruskal es un ejemplo de algoritmo voraz.
No hay comentarios:
Publicar un comentario