Détection de Cycle (graphe orienté)
DFS avec coloriage à 3 couleurs
Enonce
Implémenter a_cycle_oriente(G) qui détecte si un graphe orienté contient un cycle. Renvoie True ou False.
Tester sur un DAG (cours et prérequis) et sur un graphe avec cycle.
Signature attendue
def a_cycle_oriente(G: dict) -> bool:Exemples
a_cycle_oriente({0: [1], 1: [2], 2: [0]})→Truea_cycle_oriente({0: [1], 1: [2], 2: []})→False
📖 Rappel de cours
La détection de cycle dans un graphe orienté ne peut pas se faire avec la technique du « parent » utilisée pour le cas non orienté. Il faut distinguer trois états pour chaque sommet pendant le DFS.
Algorithme à trois couleurs :
- BLANC : sommet jamais visité
- GRIS : sommet en cours d'exploration (sur la pile DFS courante)
- NOIR : sommet entièrement traité (retour de l'appel DFS)
Pendant le DFS depuis $u$, si on tombe sur un voisin $v$ qui est GRIS, c'est qu'on revient sur un ancêtre encore en cours d'exploration → arête arrière → cycle.
Conséquence importante :
Un graphe orienté admet un tri topologique si et seulement si il est acyclique (DAG).
Tomber sur un voisin NOIR n'est pas un cycle : c'est juste une arête de traverse vers un sous-arbre déjà fini.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Plus Court Chemin dans un Labyrinthe
- Représentations d'un Graphe
- Test de Bipartisme
- Diamètre d'un Arbre
- Algorithme de Floyd-Warshall
- Composantes Fortement Connexes (Kosaraju)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.