Aprendizaje de algoritmos de gráficos

Question

En algoritmos, he sido principalmente autodidacta y eso en gran medida ha estado bien. Sin embargo, tengo problemas para captar algoritmos de gráficos. Estoy buscando algún tipo de referencia que tenga conceptos y código real, así que no solo puedo aprender la teoría (que normalmente hago bien) sino también tener una idea de cómo se representan y manipulan los gráficos en la práctica (lo que generalmente tengo) un agarre de tiempo más difícil). ¿Puede SO entregar? Cualquier cosa, desde libros hasta enlaces, a proyectos existentes sería genial, siempre que tengan tanto el concepto como la implementación.

Esto es independiente del idioma, pero estoy más familiarizado con Python y no tengo mucha experiencia con FP.

Answer 1

Ambos son muy buenos:

• The Algorithm Design Manual

• Algorithms in C++ Part 5: Graph Algorithms (No se preocupe por el bit de C++, también tiene pseudocódigo)

Materia libre:

• Chapter 5. Graphs and graph algorithms

Answer 2

Steve Yegge dice this es un excelente libro sobre algoritmos que usa gráficos extensivamente.

Answer 3

he aprendido mucho acerca de los gráficos del libro vinculado a continuación ... es uno de mis libros favoritos: http://books.google.com/books?id=5l5ps2JkyT0C&printsec=frontcover&dq=a+course+in+combinatorics&source=bl&ots=wSYYY6KPuI&sig=mZLrdj0xo2mTxW4MxYt4tW_E-10&hl=en&ei=PoHHTOaROIHGlQegn8ibAg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CCkQ6AEwAQ#v=onepage&q&f=false

A Course in Combinatorics 
J. H. van Lint, R. M. Wilson 
Cambridge University Press 
ISBN 0 521 00601 5

Answer 4

sugeriría que cuando se estudia cualquier algoritmo entonces no pensar en la codificación de la misma. Los algoritmos son totalmente matemáticos y debes tener la misma actitud hacia ellos. Cuando estudias algo así como el algoritmo Graph Spanner, entonces no pienses cómo codificarlo para representarlos. Primero, aprecie por qué el algoritmo es importante y no trivial. Luego pruebe algunas soluciones muy triviales y compare su complejidad. A continuación, vea cómo se ven las soluciones óptimas y trate de obtener sus propiedades. Use papel y bolígrafo y no IDE, intente derivar y probar lemas, etc. Luego, finalmente, vea cómo puede escribir un pseudocódigo para resolver el problema. Si haces estas cosas, desarrollarás una relación íntima con los algoritmos y luego encontrarás que es mucho más fácil resolverlos, ya que entonces no piensas al codificar por qué estoy haciendo esto.

Desafortunadamente, debido a las enormes demandas de programador, el programador de hoy en día no es matemático y tiene problemas para resolver nuevos problemas. Programador de días anteriores como Don Knuth, Mcarthy eran matemáticos y buenos investigadores. Por lo tanto, el programador es hoy una palabra relativamente barata en comparación con los científicos informáticos.

Answer 5

algoritmo Bellman-Ford: ruta más corta desde Fuente a todos los otros nodos en el gráfico dirigido ponderado incluso con peso borde -Eve (no ciclo). más lento pero versátil que Dijsktra. Complejidad: O (| V | | E |.)

BFS: Find camino de un vértice dado a otros nodos en el gráfico un-dirigido no ponderada. Complejidad: O (| V | + | E |). es más rápido cuando conoces los vértices adelante y usas la estructura de datos apropiada i.e FIFO Que para averiguar qué vértice ya procesada de la complejidad puede ser reducida a O (| V |)

DFS: Encuentra ruta más corta desde la fuente a otros nodos. en árbol y también en gráfico. El gráfico puede contener un ciclo, lo que significa que un nodo podría visitarse una y otra vez. entonces podemos usar una matriz booleana para hacer un seguimiento de los nodos visitados. de lo contrario, el algoritmo no se detendrá. más sobre ella se ve más y más profundo y llegar tan lejos al final de la rama en el árbol. Complejidad: O (| V | + | E |). y Complejidad: O (| V |) espacio para almacenar vértices.

Floyed Warshal Algoritmo: Encuentra Todo par camino más corto en Directed gráfico no ponderado con + víspera, -Eve (no ciclo) peso borde. pero no devuelve detalles de los caminos mismos. se puede usar para detectar el ciclo de peso en el gráfico. cuando encuentra uno, termina. compara todo el camino posible a través del gráfico entre cada par de vértices. por lo que utiliza el enfoque dinámico, no el enfoque codicioso. Complejidad: O (| V^3 |)

de Johnson Algoritmo: encontrar toda camino más corto par en el gráfico escasa ponderado dirigida cuando el peso borde es + víspera, ciclo -Eve -Eve pero no. primero usa el algoritmo de belman-ford para calcular el gráfico transformado del gráfico original. elimina -pestaños de peso. luego Dijkstra se aplica para encontrar caminos. Complejidad: O (V^2 Log V + VE)

Dijkstra Algoritmo: la versión original de este algoritmo no utiliza la prioridad Que así La complejidad es O (| V^2 |) pero una La versión más nueva usa esta estructura de datos para que la complejidad se convierta en O (E + V log V). y es el algoritmo de ruta más corta de origen único más rápido. funciona asignando un peso tentativo al nodo visitado e infinito a nodos no visitados para buscar los bordes visitados de todos sus bordes no visitados y seleccionar con un peso mínimo. y agregarlo al conjunto de ruta.

Algoritmo de Krushkal: para encontrar MST donde encuentra un borde del menor peso posible que conecta dos árboles en el bosque en un gráfico no dirigido y ponderado. este es un algoritmo codicioso. también encuentra Minimum Spanning Forest. Complejidad: O (E log V)

Algoritmo de Prim: que encuentra subconjunto de bordes que forman un árbol en un-dirigida, gráfico ponderado. pero no puede encontrar MS Forest como lo hace el Algoritmo de Krushkal.

Algoritmo de Brouvka: El problema con este algoritmo es que los pesos deben ser únicos en el gráfico. encuentra MST examinando cada vértice y luego colocando con menor peso. este algoritmo es de naturaleza paralela pero no más rápido que el Algoritmo de Prim.

Misma Complejidad que el Algoritmo de Krushkal.