Nous continuons ici l’étude du parcours des graphes, avec l’implémentation concrète des parcours en largeur et en profondeur et la présentation de leurs applications.
I. Parcours en profondeur
Pour effectuer le parcours d’un graphe en profondeur nous utilisons une structure de pile. Cette pile contient initialement le sommet de départ. Tant qu’elle n’est pas vide, nous dépilons son sommet et regardons s’il a déjà été exploré. Si ce n’est pas le cas, nous le rajoutons à la liste des sommets déjà visités (initialement vide) et empilons tous ses voisins. Lorsque la pile est vide, la liste des sommets visités donne le parcours en profondeur du graphe.
Nous utilisons la classe GrapheLS. Une liste vus contient les sommets déjà visités, une liste parc donne le parcours effectué. La structure de pile est modélisée avec une liste voisins. Le sommet de la pile est le dernier élément de la liste, de sorte à pouvoir le supprimer en temps constant. Les voisins sont empilés à l’envers, de sorte que le premier voisin est en fin de la liste voisins ; ceci est réalisé en inversant la liste des voisins du sommet exploré à l’aide de la méthode lst.reverse().
Le parcours en profondeur permet de trouver la composante connexe d’un sommet (tous ses sommets accessibles). Il est également utilisé pour répondre au problème du tri topologique d’un graphe orienté, qui permet de donner un ordre dans lequel peuvent être effectuées des tâches dont la réalisation dépend d’autres tâches.
II. Parcours en largeur
Pour effectuer le parcours d’un graphe en largeur, nous utilisons une structure de file.
Cette file contient initialement le sommet de départ. Tant qu’elle n’est pas vide, nous traitons le premier sommet et regardons s’il a déjà été exploré. Si ce n’est pas le cas, nous le rajoutons à la liste des sommets déjà visités (initialement vide) et mettons dans la file d’attente tous ses voisins. Lorsque la file est vide, la liste des sommets visités donne le parcours en largeur du graphe.
Nous utilisons la classe GrapheLS. Une liste vus contient les sommets déjà visités, une liste parc donne le parcours effectué. La structure de file est modélisée avec une liste voisins. Le premier élément de la liste est celui à traiter en priorité dans la file. Il est supprimé et récupéré à l’aide de la méthode voisins.pop(0), ce qui n’est malheureusement pas optimal dans la mesure où cette opération est en temps linéaire. Les voisins sont mis dans l’ordre à la fin de la liste voisins.
Le parcours en largeur d’un graphe permet aussi de trouver la composante connexe d’un sommet. Il permet également de trouver tous les plus courts chemins à partir d’un sommet, ce qui peut être utilisé pour trouver de manière optimale la sortie d’un labyrinthe.
III. Parcours des graphes pondérés.
L’algorithme de Dijkstra permet de trouver le plus court chemin à partir d’un sommet dans un graphe pondéré orienté ou non dont les pondérations sont positives. Il est notamment utilisé pour le routage internet, mais aussi pour le guidage GPS, des problèmes d’optimisation, etc.
Lorsque le nombre de sommets du graphe est trop important, l’algorithme de Dijkstra devient inefficace. D’autres algorithmes existent qui ne donnent pas forcément une solution optimale : l’algorithme A* par exemple.