Parcourir les graphes

Un sommet représente un objet et une arête une relation non orientée. Dans un graphe orienté, un arc indique un sens autorisé : pouvoir aller de A vers B ne garantit pas le retour. Une liste d’adjacence associe à chaque sommet ses voisins, ou ses successeurs dans le cas orienté. Tous les sommets, y compris les sommets isolés, doivent apparaître comme clés du dictionnaire. On suppose ici des graphes simples, sans boucle ni arêtes multiples.

Pour le graphe dessiné, les listes, dans cet ordre, sont A : B, C ; B : A, D ; C : A, D, E ; D : B, C ; E : C. Chaque arête apparaît dans deux listes parce que le graphe est non orienté. L’ordre des voisins détermine les choix quand plusieurs déplacements sont possibles. Il faut donc le préciser pour donner un ordre de parcours unique ; le dessin seul ne suffit pas à l’imposer.

Un chemin est une succession de sommets reliés, respectant les orientations éventuelles. Sa longueur compte les arêtes, et non les sommets. Un chemin de A vers A peut être vide et avoir longueur zéro. Un cycle simple revient à son point de départ sans répéter les autres sommets. Parcourir depuis une origine atteint seulement les sommets accessibles depuis elle ; un graphe non connexe nécessite plusieurs départs pour être exploré entièrement.

Le parcours en largeur utilise une file : le premier sommet entré est le premier retiré. On découvre d’abord l’origine, puis tous ses voisins, puis les sommets encore inconnus atteints à partir de ces voisins. Marquer un sommet dès son entrée dans la file empêche de l’ajouter plusieurs fois. Être découvert signifie être connu du parcours ; être traité signifie avoir examiné ses voisins. Ces deux moments sont différents.

Pourquoi la première distance trouvée est-elle minimale ? Tous les sommets de distance zéro sont traités avant ceux de distance un, puis ceux de distance un avant ceux de distance deux. Si un sommet était accessible par un chemin plus court, il aurait été découvert lors d’un niveau antérieur. Ce raisonnement concerne le nombre d’arêtes. Quand des arêtes portent des durées différentes, la largeur ne garantit pas la durée minimale.

Le parcours en profondeur suit une branche jusqu’à ne plus pouvoir avancer, puis revient au dernier choix encore disponible. Une fonction récursive réalise ce comportement grâce à la pile des appels. À l’entrée dans un sommet, elle le marque ; elle appelle ensuite la même fonction pour chaque voisin non marqué, dans l’ordre fixé. Un appel se termine quand tous les voisins ont été examinés.

Pour reconstruire un chemin, mémorise pour chaque nouveau sommet le prédécesseur qui l’a découvert. Pars de la destination, remonte jusqu’au départ et renverse la liste obtenue. Si la destination n’a pas été découverte, annonce qu’aucun chemin n’existe depuis cette origine. Ne fabrique pas un chemin en reliant arbitrairement les sommets successifs de l’ordre de parcours : deux sommets traités consécutivement ne sont pas forcément voisins.

Avec des listes d’adjacence, chaque sommet est découvert une fois et chaque liste est parcourue une fois. Le coût est donc O(n + m), pour n sommets et m arêtes, avec un ensemble permettant une recherche efficace. Dans un graphe non orienté, chaque arête est examinée deux fois, ce qui ne change pas cet ordre de grandeur. Une matrice impose au contraire de regarder une ligne de n cases par sommet.

Dans un graphe simple non orienté, chaque arête apparaît aussi dans le sens du retour. Pendant un parcours récursif en profondeur, retrouver le parent du sommet courant n’indique donc pas un cycle. En revanche, rencontrer un autre voisin déjà découvert révèle un cycle. Il faut retenir le parent et distinguer ces deux cas. Pour chercher un cycle dans tout le graphe, répète cette exploration depuis chaque sommet encore inconnu.

Dans un graphe orienté, un sommet déjà terminé peut être rejoint sans créer de cycle. On utilise trois états : non découvert, en cours d’exploration, terminé. Un arc vers un sommet en cours d’exploration referme une branche active et révèle un cycle orienté. Un arc vers un sommet terminé ne suffit pas. Cette distinction est essentielle dans un graphe de dépendances, où plusieurs tâches peuvent dépendre d’une même tâche déjà traitée.

En Python, une file peut être implémentée avec collections.deque, append pour enfiler et popleft pour défiler. Une liste avec pop(0) déplace ses éléments et dégrade le coût. Pour une exploration récursive, créer un nouvel ensemble de visités à chaque appel détruit la mémoire commune ; il faut partager cet ensemble entre les appels du même parcours. Une très longue chaîne peut aussi dépasser la limite pratique de récursion : une pile explicite permet de maîtriser cet aspect.

Pour poursuivre ton entraînement, ouvre la rubrique S’entraîner du site, à l’adresse /exercices. Reprends d’abord les questions de cette leçon sans afficher les réponses, puis compare ton raisonnement à la correction.