Détection de Cycles dans un Graphe

Pseudocode

Les graphes orientés et non orientés exigent des tests réellement différents. La version orientée suit la pile de récursion; la version non orientée suit le parent.

// Orienté: DFS à trois couleurs
BLANC = non visité, GRIS = dans la pile, NOIR = terminé

aUnCycle(u):
    couleur[u] = GRIS
    pour chaque voisin v de u:
        si couleur[v] == GRIS: renvoyer vrai   // arête arrière
        si couleur[v] == BLANC et aUnCycle(v):
            renvoyer vrai
    couleur[u] = NOIR
    renvoyer faux

// Non orienté: DFS transportant le parent
aUnCycle(u, parent):
    visites.ajouter(u)
    pour chaque voisin v de u:
        si v == parent: continuer
        si v dans visites: renvoyer vrai
        si aUnCycle(v, u): renvoyer vrai
    renvoyer faux

La distinction pèse plus lourd qu'il n'y paraît. Dans un graphe orienté, atteindre un sommet NOIR correspond à une arête transverse et ne comporte aucun cycle, si bien que le test naïf des visités signale des cycles inexistants. Dans un graphe non orienté, sauter le parent est précisément ce qui empêche de lire chaque arête comme un cycle à deux sommets.

Exemple détaillé, étape par étape

Exécute le test orienté à trois couleurs sur un graphe contenant un cycle et une arête transverse trompeuse.

Graphe d'exemple: Arêtes orientées A vers B, A vers C, B vers D, C vers D et D vers B.

1. Entrer dans A. couleur[A] = GRIS. Prends le premier voisin, B.
2. Entrer dans B. couleur[B] = GRIS. Son unique voisin est D.
3. Entrer dans D. couleur[D] = GRIS. Son voisin est B, et couleur[B] vaut GRIS. B se trouve dans la pile de récursion courante, donc D vers B est une arête arrière et le cycle B vers D vers B est confirmé.
4. Ce que ferait la version naïve. Suppose que l'arête D vers B n'existe pas. D terminerait en NOIR, le contrôle remonterait vers A, et A vers C vers D trouverait D déjà visité. Un simple test des visités appellerait cela un cycle. Ce n'en est pas un: c'est une arête transverse vers un sous-arbre terminé, et le test à trois couleurs l'ignore correctement parce que D est NOIR et non GRIS.

Le graphe contient bien un cycle, B vers D vers B, trouvé grâce au test GRIS. Le chemin A vers C vers D n'est pas un cycle, et seule la distinction de couleurs sépare les deux cas.

Complexité et son origine

Temps: O(V + E) · Espace: O(V)

Les deux variantes sont un unique DFS avec un travail supplémentaire constant par arête, le coût est donc celui du parcours. Le tableau des couleurs ou l'ensemble des visités est en O(V), plus O(V) de pile de récursion. L'alternative Union-Find pour les graphes non orientés tourne en O(E alpha(V)), pratiquement linéaire, et devient préférable quand les arêtes arrivent une à une et que tu veux rejeter l'arête fermant le cycle au moment où elle apparaît, sans reparcourir tout le graphe.

Quand utiliser Détection de Cycles, et quand l'éviter

Choisis le test correspondant à la fois à l'orientation de tes arêtes et au fait que le graphe soit statique ou construit au fil de l'eau.

Pièges fréquents

• Utiliser le test non orienté sur un graphe orienté. C'est de loin l'erreur la plus fréquente en détection de cycles. Un simple test des visités sur un graphe orienté signale un cycle pour toute arête transverse vers un sous-arbre déjà terminé. Utilise trois couleurs, ou maintiens la pile de récursion comme ensemble distinct.
• Oublier de réinitialiser la marque de pile de récursion. La marque GRIS doit passer à NOIR quand le sommet termine. Laisser des sommets en GRIS fait ressembler tout chemin ultérieur vers eux à une arête arrière, ce qui produit des faux positifs dès la deuxième racine du DFS.
• Ne pas repartir sur les composantes déconnectées. Un DFS depuis une source ne voit qu'une composante. Le cycle peut se trouver dans une composante que tu n'as jamais visitée, alors parcours tous les sommets et relance un DFS depuis chacun de ceux encore non visités.
• Boucles et arêtes parallèles. Une boucle sur soi-même est un cycle de longueur un que le test du parent ne détecte pas. Deux arêtes parallèles entre la même paire forment un cycle de longueur deux dans un multigraphe non orienté, mais sauter le parent sans condition le masque. Saute l'arête du parent une seule fois, pas à chaque occurrence.

Questions fréquentes

Comment détecter un cycle dans un graphe orienté?

Exécute un DFS colorant les sommets en blanc, gris et noir. Un sommet est gris tant qu'il figure dans la pile de récursion courante, et noir une fois terminé. Une arête vers un sommet gris est une arête arrière et prouve un cycle. Une arête vers un sommet noir est transverse ou avant et ne prouve rien. Le test complet est en O(V + E).

Comment détecter un cycle dans un graphe non orienté?

Exécute un DFS transportant le parent de chaque sommet. Si tu atteins un sommet déjà visité qui n'est pas le parent, cette arête ferme un cycle. Autre possibilité, Union-Find: traite les arêtes une à une et signale un cycle dès que les deux extrémités appartiennent déjà au même ensemble.

Pourquoi le test des visités échoue-t-il sur les graphes orientés?

Parce qu'être visité signifie seulement que le sommet a été atteint plus tôt, non qu'il soit un ancêtre du sommet courant. Dans le graphe A vers B, A vers C, B vers D, C vers D il n'y a aucun cycle, et pourtant un simple test des visités signale l'arête C vers D parce que D avait déjà été vu via B. Il faut savoir si la cible figure encore dans la pile de récursion.

Quelle est la façon la plus rapide de détecter un cycle?

Pour un graphe statique, un unique DFS en O(V + E) est optimal, puisqu'il faut au minimum lire l'entrée. Pour un graphe non orienté construit arête par arête, Union-Find est meilleur en pratique car chaque arête ajoutée est testée en temps quasi constant sans reparcours.

Un DAG peut-il contenir un cycle?

Non, par définition. Un graphe orienté acyclique est précisément un graphe orienté sans cycle, et c'est pourquoi la détection de cycles est la vérification de validité standard avant un tri topologique. S'il existe un cycle, aucun ordre topologique valide n'existe.