Détection de cycle

Algo 19

Résumé du cours

À retenir

Dans un graphe, un cycle est un chemin qui part d’un sommet et revient à ce même sommet.

Pour détecter un cycle il faut définir trois états pour chaque sommet:

  • BLANC : sommet non encore atteint,
  • GRIS : sommet en cours de visite,
  • NOIR : sommet dont le parcours est terminé

Algorithme du parcours en profondeur modifié:

  • Si le sommet est GRIS renvoyer Vrai.
  • Si le sommet est NOIR renvoyer Faux.
  • Marquer le sommet GRIS.
  • Pour tous les sommets voisins :
    • Effectuer récursivement un parcours en profondeur.
    • Si le parcours est un cycle, renvoyer Vrai.
  • Marquer le sommet NOIR.
  • Renvoyer Faux.

Chaque sommet n’est pas nécessairement atteignable depuis n’importe quel sommet de départ. Il faut donc effectuer un parcours en profondeur depuis tous les sommets:

  • Initialiser chaque sommet à BLANC.
  • Pour chaque sommet :
    • Effectuer un parcours en profondeur.
    • Si le parcours est un cycle, renvoyer Vrai.
  • Renvoyer Faux