Comment détecter un cycle lors d’un parcours de graphe non orienté ?
Réponse courte
Pendant un parcours en profondeur d’un graphe non orienté simple, un sommet courant révèle un cycle s’il rencontre un voisin déjà découvert qui n’est pas son parent. Le retour vers le parent suit simplement l’arête d’arrivée.
Comprendre
Pourquoi noter le parent ?
Dans un graphe non orienté, chaque arête est parcourable dans les deux sens. Après avoir découvert B depuis A, le parcours de B retrouve A dans sa liste de voisins. Ce retour ne forme pas un cycle : c’est la même arête AB. Il faut donc mémoriser le parent de chaque sommet dans l’arbre de parcours.
Le critère de détection
Lorsqu’un sommet examine un voisin déjà découvert, compare ce voisin à son parent. S’il s’agit du parent, continue sans signaler de cycle. S’il s’agit d’un autre sommet, le parcours a trouvé un autre chemin vers un sommet déjà atteint : il existe alors un cycle. Dans le triangle A–B–C–A, depuis C, A est déjà découvert et n’est pas le parent B ; le cycle A–B–C–A est détecté.
Explorer tout le graphe
Un départ ne couvre que la composante accessible. Pour décider si le graphe entier contient un cycle, lance le parcours depuis chaque sommet encore non découvert. Le critère décrit ici suppose un graphe simple non orienté, sans boucle ni arêtes multiples. Pour un graphe orienté, il faut une autre règle, qui distingue notamment les sommets encore en cours d’exploration de ceux déjà terminés.
Exemples
- Dans l’arête seule A–B, B retrouve A, son parent : ce retour ne déclenche pas de détection de cycle.
- Dans le triangle A–B, B–C, C–A, C rencontre A déjà découvert et différent de son parent B : un cycle existe.
- Dans un graphe non orienté comportant deux composantes, un parcours lancé seulement depuis la première ne peut pas conclure à l’absence de cycle dans la seconde.
Pièges fréquents
- Signaler un cycle dès qu’un sommet voit n’importe quel voisin déjà marqué produit un faux positif, car l’arête vers le parent est aussi présente en sens inverse.
- Appliquer ce critère à un graphe orienté est incorrect : l’état d’un sommet terminé ou encore actif change l’interprétation d’un arc.
Pourquoi ça marche
Dans une exploration en profondeur non orientée, un voisin déjà atteint qui n’est pas le parent fournit un chemin de retour distinct ; combiné au chemin courant, il ferme un cycle.
