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(conjunto de
á
rboles), donde cada vértice del grafo es un árbol separado.
Se crea un conjunto C donde tenga todo el conjunto de aristas.
Mientras C no es
vacío
Eliminar una arista de peso mínimo de C
Si esa arista conecta dos
á
rboles diferentes se agrega el bosque, combinando los
á
rboles diferentes se agrega el bosque.
En caso contrario se desecha la arista.
Aplicaciones
Las aplicaciones mas comunes que se utilizan para este algoritmo, son para ahorrar recursos, como en circuitos eléctricos, conexiones, entre otras...
Aquí un ejemplo de su aplicación:
Supongamos que una empresa de telefonía, brinda 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 brindar el servicio, y la linea negra, son las aristas, que es el cable necesario a usarse.
Ahora hay que buscar cual ser
í
a la menor cantidad de cable que se debera usar.
Aquí esta un código que se empleo
Bibliografia:
ResponderEliminarwww.mincel.com/java/prim.html
http://www.cut-the-knot.org/Curriculum/Games/Mazes.shtml