El algoritmo de Kruskal es un algoritmo (ávido) de la teoría de grafos para encontrar un árbol de recubriumiento 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
En este caso me limitaré al caso de grafos conexos con costos no negativos en sus aristas
Funcionamiento:
Se parte colocando todos los vértices del grafo separados, y se decide partir por un vértice de "Inicio".
Dado el vértice actual (en el comienzo es el de inicio), armamos una lista de todas las aristas que posee, ordenadas en forma decreciente según su ponderación (costo de la arista).
Tomamos la de menor coste, retiramos de la lista de candidatos a la arista utilizada y agregamos las nuevas aristas que nos proporciona el nuevo vértice.
Así sucesivamente, generando subgrafos conexos hasta llegar a conectar todos los subgrafos conexos formando un Árbol de cubrimiento de costo mínimo.
Un excelente ejemplo se encuentra en el artículo dedicado a este algoritmo en wikipedia
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
En este caso me limitaré al caso de grafos conexos con costos no negativos en sus aristas
Funcionamiento:
Se parte colocando todos los vértices del grafo separados, y se decide partir por un vértice de "Inicio".
Dado el vértice actual (en el comienzo es el de inicio), armamos una lista de todas las aristas que posee, ordenadas en forma decreciente según su ponderación (costo de la arista).
Tomamos la de menor coste, retiramos de la lista de candidatos a la arista utilizada y agregamos las nuevas aristas que nos proporciona el nuevo vértice.
Así sucesivamente, generando subgrafos conexos hasta llegar a conectar todos los subgrafos conexos formando un Árbol de cubrimiento de costo mínimo.
Un excelente ejemplo se encuentra en el artículo dedicado a este algoritmo en wikipedia
1 comentario:
Ha sido de gran ayuda esta breve y clara explicacion del algoritmo.. era lo que buscaba.. Muy buen blog..!
Publicar un comentario