Mes Projets Informatiques
Informatique II : Devoir d'Algorithmique de Graphe
Dans le cadre de ma formation d’ingénieur, je suis amenés à suivre un cours d’algorithmique des graphes. A travers ce cours, j'aborde des notions inhérentes aux graphes. je suis alors amené à manipuler des graphes afin de déterminer, entres autres, le plus court chemin entre deux sommets, ou bien de déterminer les composantes fortement connexes.
Voici l'application en fonctionnement. On voit ici un exemple de graphe codé en dur dans l'application. Un bouton situé dans la barre supérieur permettant d'appliquer l'algorithme de recherche des composantes fortement connexes peut être pressé. En outre, différentes fonctionnalités implémentées permettent par exemple de déplacer les sommets, d'ajouter des arcs, etc...
Voici un graphe représentant les composantes fortement connexes d'un graphe.
Ainsi, l'application, codée en JAVA et avec interface graphique, permet de déterminer ces composantes. Elle utilise ainsi l'algorithme de Kosaraju-Sharir pour déterminer ces composantes. Ainsi, elle calcule dans un premier temps le DFS du graphe (graphe pouvant être codé en dur dans l'application, ou bien créer, point par point et arc par arc à partir de l'interface graphique en quelques clics de souris) afin de déterminer la numérotation suffixe des sommets. Elle inverse ensuite le sens de tous les arcs. Enfin, l'application recalcule ensuite le DFS sur le graphe aux arcs inversés en utilisant la numérotation suffixe précédemment effectuée. On peut alors déterminer les différentes composantes connexes simplement en remarquant lorsque l'application distingue un point de régénération.
Un rapport complet présente plus en détail le travail effectué. Je vous invite donc à le consulter. Le code source de l'application est disponible. Vous pouvez également récupérer l'archive complète du code.
