Manière efficace de pratiquer les algorithmes de la théorie des graphes

Question

Je viens de lire l'algorithme breadth-first search dans le livre Introduction to Algorithms et j'ai simulé l'algorithme sur papier. Ce que je voudrais faire maintenant, c'est de l'implémenter dans du code pour une pratique supplémentaire. Je pensais à implémenter toutes les structures de données à partir de zéro (les adjacency list, les tableaux "couleur", "distance" et "parent") mais je me suis souvenu qu'il y a actuellement des bibliothèques de graphes comme le Boost bibliothèque et un autre graph APIs en Python. J'ai également essayé de chercher des problèmes liés à BFS sur UVA et Sphere Judge Online mais je ne peux pas dire quels problèmes nécessiteraient une solution BFS.

Ma question est quelle serait la façon la plus indolore pour pratiquer ces algorithmes de graphes (et pas seulement limité à BFS, mais aussi bien utile quand je veux mettre en œuvre DFS, Dijkstra, Floyd-Warshall, etc.). Les sites ayant des problèmes de pratique sont les bienvenus.

Answer 1

Personnellement, je pense que la meilleure façon de comprendre cela serait d'implémenter la représentation graphique à partir de zéro. D'une part, cela vous montrerait les mises en œuvre réelles à partir desquelles vous apprendrez pourquoi ou pourquoi pas un algorithme particulier pourrait être intéressant/bon/efficace/peu importe. D'un autre côté, je pense que la compréhension des graphes et leur utilisation réelle, y compris ses implications (récursivité, performances/évolutivité, applications, alternatives, ...), sont facilitées par l'approche ascendante.

Mais peut-être que c'est juste moi. Ce qui précède est un goût très personnel.

Answer 2

J'ai trouvé votre question intéressante, j'ai googlé un peu et j'ai trouvé JGraphEd.

Il ne couvre pas tous les algorithmes de graphes mais il semble être un bon outil d'expérimentation.

Answer 3

Je suis d'accord avec balpha. La meilleure façon d'apprendre et de comprendre les algorithmes est de faire l'implémentation. Il suffit de choisir un algorithme et de l'implémenter. Lorsque vous atteignez un point où vous êtes bloqué ou incertain, regardez un certain nombre d'exemples existants. Vous serez alors en mesure de comparer votre propre pensée avec celle des autres à partir d'une position de compréhension au lieu d'accepter simplement ce qui est offert. Une fois que vous avez appris ce que vous voulez, la meilleure façon de consolider votre compréhension est d'essayer de l'enseigner ou de la décrire à quelqu'un d'autre. Vous pourriez avoir des gens prêts à vous écouter, ou à tout le moins vous pourriez écrire une entrée de blog pour les personnes nouvelles à l'algorithme que vous venez d'étudier.

Mais si vous cherchez « indolore », alors peut-être vous devriez rester à l'écart des algorithmes tout à fait ;-)

Answer 4

This site could help you

Ici vous avez la description de chaque problème sur problemset acm. Vous pouvez voir la catégorie de chaque problème, et un indice pour le résoudre. Il suffit de parcourir les problèmes liés aux graphiques. Un bon conseil est d'utiliser ces conseils seulement si vous avez essayé de résoudre le problème vous-même et échoué.

Answer 5

Visualisation de certains algorithmes de plus court chemin sur des données réelles, où la zone explorée est affichée en jaune:

• (bidirectional) Dijkstra
• A*