Manera eficiente de practicar algoritmos de teoría de grafos

Question

Acabo de leer sobre el algoritmo breadth-first search en el libro de Introducción a Algoritmos y simulé el algoritmo en papel. Lo que me gustaría hacer ahora es implementarlo en el código para una práctica adicional.

Estaba pensando en implementar todas las estructuras de datos desde cero (adjacency list, las matrices de "color", "distancia" y "principal") pero entonces recordé que actualmente hay bibliotecas de gráficos como Boost graph biblioteca y alguna otra graph APIs en Python. También traté de buscar algunos problemas relacionados con BFS en UVA y Sphere Judge Online pero no puedo decir qué problemas requerirían una solución BFS.

Mi pregunta es ¿cuál sería la forma más indolora para practicar estos algoritmos de grafos (no sólo limitado a BFS, sino que también será muy útil cuando quiero poner en práctica DFS, Dijkstra, Floyd-Warshall, etc). Los sitios con problemas de práctica son bienvenidos.

Answer 1

Personalmente, creo que la mejor manera de entenderlos sería implementar la representación del gráfico desde cero.

Por un lado, eso mostraría las advertencias de implementación reales de las cuales usted aprende por qué o por qué no un algoritmo en particular podría ser interesante/bueno/eficiente/lo que sea. Por otro lado, creo que la comprensión de los gráficos y su uso en la vida real, incluidas sus implicaciones (recursión, rendimiento/escalabilidad, aplicaciones, alternativas, ...), se facilita mediante el enfoque ascendente.

Pero tal vez sea solo yo. Lo anterior es un gusto muy personal.

Answer 2

Me pareció interesante su pregunta, busqué en Google un poco y encontré JGraphEd.

No cubre todos los algoritmos de gráficos, pero parece una buena herramienta para la experimentación.

Answer 3

Estoy de acuerdo con balpha. La mejor forma de aprender y entender algoritmos es hacer la implementación. Solo elige un algoritmo e impleméntalo. Cuando llegas a un punto en el que te quedas atascado o no estás seguro, mira una cantidad de ejemplos existentes. Entonces podrá comparar su propio pensamiento con el de los demás desde una posición de comprensión en lugar de simplemente aceptar lo que se le ofrece.

Una vez que haya aprendido lo que quiere, la mejor manera de consolidar su comprensión es intentar enseñarlo o describirlo a otra persona. Es posible que haya personas dispuestas a escucharte o, como mínimo, que puedas escribir una entrada en el blog para personas que conozcan el algoritmo que acabas de estudiar.

Pero si se busca "sin dolor", entonces tal vez debería mantenerse alejados de los algoritmos por completo ;-)

Answer 4

This site could help you

Aquí tienes descripción de todos los problemas en Boletín de problemas acm. Puedes ver la categoría de cada problema y una pista para resolverlo. Solo busque problemas relacionados con los gráficos. Un buen consejo es usar esas sugerencias solo si trataste de resolver el problema tú mismo y fracasaste.

Answer 5

La visualización de algunos algoritmos del camino más corto en datos reales, donde se muestra el área explorada en amarillo:

• (bidirectional) Dijkstra
• A*