Code--Blocks + Grafos Algoritmos C++

Estudias o tenes pensado estudiar Ingeniería en sistemas? no te olvides de visitar CUYS



http://www.comoustedyasabe.com.ar/

Hola amigos aca les traigo algunos algoritmos de grafos paso a paso de como pensarlos en hoja + los Codigos Fuente, información, vídeos e imágenes

Atencion

Aca les dejo todo lo que esta en el Post en un archivo.rar que subi yo a Megaupload
contiene los videos / imagenes mas descripciones y el codigo echo en C++
Ademas de contener los códigos e información de Kruscal, Prim, Floyd, Dijkstra. Contiene la Clase Grafo, el Ciclo Hamiltoniano, el DFS Y BFS y Ordenamiento Topologico

Linck: http://www.megaupload.com/?d=QPWOUEU4

Seguramente se estarán preguntando que use para Programar y Compilar los Algoritmos

pues no desesperen, acá esta el programa Code::Blocks 10.5
Versión Windows 2000/xp/vista/seven: http://bit.ly/eJayf4
Versión Mac: http://bit.ly/dIiFTB

Ahora si empecemos con el Post

Dijkstra

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).






link: http://www.youtube.com/watch?v=6rl0ghgPfK0&feature=feedlik

Floyd

El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. El algoritmo es capaz de hacer esto con sólo V3 comparaciones (esto es notable considerando que puede haber hasta V2 aristas en el grafo, y que cada combinación de aristas se prueba). Lo hace mejorando paulatinamente una estimación del camino más corto entre dos vértices, hasta que se sabe que la estimación es óptima.

Sea un grafo G con conjunto de vértices V, numerados de 1 a N. Sea además una función caminoMinimo(i,j,k) que devuelve el camino mínimo de i a j usando únicamente los vértices de 1 a k como puntos intermedios en el camino. Ahora, dada esta función, nuestro objetivo es encontrar el camino mínimo desde cada i a cada j usando únicamente los vértices de 1 hasta k + 1.
Hay dos candidatos para este camino: un camino mínimo, que utiliza únicamente los vértices del conjunto (1...k); o bien existe un camino que va desde i hasta k + 1, después de k + 1 hasta j que es mejor. Sabemos que el camino óptimo de i a j que únicamente utiliza los vértices de 1 hasta k está definido por caminoMinimo(i,j,k), y está claro que si hubiera un camino mejor de i a k + 1 a j, la longitud de este camino sería la concatenación del camino mínimo de i a k + 1 (utilizando vértices de (1...k)) y el camino mínimo de k + 1 a j (que también utiliza los vértices en (1...k)).

Floyd parte 1



link: http://www.youtube.com/watch?v=qdY4vK1V0Nk&feature=related

Floyd parte 2



link: http://www.youtube.com/watch?v=mk62s7W0kN8&feature=related

Kruskal

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 total 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). El algoritmo de Kruskal es un ejemplo de algoritmo voraz.

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
Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

Ejemplo
Este es el grafo original. Los números de las aristas indican su peso. Ninguna de las aristas está resaltada.


AD y CE son las aristas más cortas, con peso 5, y AD se ha elegido arbitrariamente, por tanto se resalta


Sin embargo, ahora es CE la arista más pequeña que no forma ciclos, con peso 5, por lo que se resalta como segunda arista.


La siguiente arista, DF con peso 6, ha sido resaltada utilizando el mismo método.


La siguientes aristas más pequeñas son AB y BE, ambas con peso 7. AB se elige arbitrariamente, y se resalta. La arista BD se resalta en rojo, porque formaría un ciclo ABD si se hubiera elegido.


El proceso continúa marcando las aristas, BE con peso 7. Muchas otras aristas se marcan en rojo en este paso: BC (formaría el ciclo BCE), DE (formaría el ciclo DEBA), y FE (formaría el ciclo FEBAD).


Finalmente, el proceso termina con la arista EG de peso 9, y se ha encontrado el árbol expandido mínimo.



Prim

El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.
El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar

Ejemplo

Este es el grafo ponderado de partida. No es un árbol ya que requiere que no haya ciclos y en este grafo los hay. Los números cerca de las aristas indican el peso. Ninguna de las aristas está marcada, y el vértice D ha sido elegido arbitrariamente como el punto de partida.


El segundo vértice es el más cercano a D: A está a 5 de distancia, B a 9, E a 15 y F a 6. De estos, 5 es el valor más pequeño, así que marcamos la arista DA.


El próximo vértice a elegir es el más cercano a D o A. B está a 9 de distancia de D y a 7 de A, E está a 15, y F está a 6. 6 es el valor más pequeño, así que marcamos el vértice F y a la arista DF.


El algoritmo continua. El vértice B, que está a una distancia de 7 de A, es el siguiente marcado. En este punto la arista DB es marcada en rojo porque sus dos extremos ya están en el árbol y por lo tanto no podrá ser utilizado.


Aquí hay que elegir entre C, E y G. C está a 8 de distancia de B, E está a 7 de distancia de B, y G está a 11 de distancia de F. E está más cerca, entonces marcamos el vértice E y la arista EB. Otras dos aristas fueron marcadas en rojo porque ambos vértices que unen fueron agregados al árbol.


Sólo quedan disponibles C y G. C está a 5 de distancia de E, y G a 9 de distancia de E. Se elige C, y se marca con el arco EC. El arco BC también se marca con rojo.


G es el único vértice pendiente, y está más cerca de E que de F, así que se agrega EG al árbol. Todos los vértices están ya marcados, el árbol de expansión mínimo se muestra en verde. En este caso con un peso de 39.







http://www.comoustedyasabe.com.ar/
No olvides visitar de nuevo Code--Blocks + Grafos Algoritmos C++