Que tal gente esta vez venimos a hablarles acerca del algoritmo de kruskal y bien esta vez fue el algoritmo lo explicaremos paso a paso para mayor entendimiento y puedan comprender lo que hace.

aquí les dejare la liga para la descarga directa. descargar

Acerca de esto
Este es un algoritmo de los grafos, su intención es la de encontrar el camino mas corto(con menos recursos) llegando a todos los nodos, una de sus características de este algoritmo es de que al finalizar su resultado no tendrá ciclos, así que sera un árbol.


Funciona de la siguiente manera:
se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado
* se crea un conjunto C que contenga a todas las aristas del grafo
* mientras C es no vacío
* eliminar una arista de peso mínimo de C
* si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol
* en caso contrario, se desecha la arista.


Aplicaciones.
Las aplicaciones mas comunes que se utilizan en este algoritmo son para ahorrar recursos, como en circuitos eléctricos, conexiones, entre otras...



Aquí un ejemplo de su aplicación
Supongamos que una compañía de teléfono va a brindar servicio a sus clientes, tómese, los nodos azules son los postes de teléfono, y los nodos naranjas, son el lugar donde se quiere dar el servicio, y la linea negra, seria el cable necesario a usarse...





Ahora hay que encontrar cual sería la menor cantidad de cable que se puede utilizar.



Aquí si quieres hay paginas donde vienen animaciones, para que entiendas mejor

Kruskal

View more documents from Jorge.

www.mincel.com/java/prim.html
http://www.cut-the-knot.org/Curriculum/Games/Mazes.shtml