Mostrar los tags: kruskal

La presente aplicación tiene el objetivo de implementar el algoritmo de KRUSKAL, para
lograr encontrar el árbol recubridor con peso minimal posible.

Esta aplicación generara 4
salidas: La Matriz de adyacencia, El Grafo o Subgrafo original, el árbol recubridor de peso
minimal y el respectivo peso minimal.


Créditos a los creadores :

DAVID YZAGUIRRE GONZALEZ
ERICK ROBERTO DOMINGUEZ ALDI

Archivo originalmente posteado de
http://metalvegetarianoprogresivo.blogspot.com
http://taringa.net
:)

El 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 de la suma de todas las aristas del árbol es el mínimo.

Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa).

Les comparto un programa del "Algoritmo de Kruskal" enfocado a la teoría de grafos realizado en Java.


Espero que les sea de utilidad.