Détection de Cycle dans un Graphe Non Orienté
DFS avec parent pour détecter les arêtes arrière
Enonce
Détecter si un graphe non orienté contient un cycle. Retourner True ou False.
Tester sur un graphe avec cycle et un arbre (sans cycle).
Signature attendue
def a_cycle(G: dict) -> bool:Exemples
a_cycle({0:[1,2], 1:[0,2], 2:[0,1]})→Truea_cycle({0:[1,2], 1:[0], 2:[0,3], 3:[2]})→False
📖 Rappel de cours
Dans un graphe non orienté, un cycle existe si et seulement si lors d'un DFS, on rencontre un sommet déjà visité qui n'est pas le parent.
Principe (DFS) :
On parcourt le graphe en DFS. Pour chaque voisin $v$ du sommet courant $u$ :
- Si $v$ est visité et $v \neq \text{parent}(u)$ → cycle détecté.
Propriété :
Un graphe connexe de $n$ sommets a un cycle ssi $|E| \geq n$.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- BFS et DFS
- Algorithme de Dijkstra
- Composantes Connexes
- Tri Topologique
- Algorithme de Bellman-Ford
- Algorithme de Prim
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.