Détecter les cycles dans les graphes orientés
Colorer les nœuds pour trouver les arêtes de retour
Détecter les cycles dans les graphes orientés est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Pourquoi les cycles sont importants
Un cycle orienté signifie que les dépendances reviennent sur elles-mêmes. En détecter un vous indique qu’aucun ordre topologique ni aucun calendrier valide ne peut exister.
Les graphes non orientés sont différents
La détection des cycles porte ici sur la direction. Suivre une arête dans le mauvais sens ne compte pas : les techniques des graphes non orientés ne s’appliquent donc pas.
L’idée des trois couleurs
Attribuez à chaque nœud l’une de trois couleurs : blanc signifie non visité, gris signifie en cours de traitement et noir signifie complètement traité.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nGris signifie présent dans la pile
Un nœud gris se trouve sur le chemin DFS actuel. Vous y êtes entré, mais vous n’avez pas encore fini d’explorer tous ses descendants.
Entrer dans un nœud
Lorsque DFS atteint un nœud, colorez-le en gris avant de l’explorer. Vous le marquez ainsi comme faisant partie du chemin actif.
def dfs(u):
color[u] = GRAYLe signal de l’arête de retour
Si vous atteignez un voisin déjà gris, vous avez trouvé une arête de retour vers le chemin actuel. Il s’agit d’un cycle.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleRecommencer dans les nœuds blancs
Un voisin blanc est nouveau, alors descendez récursivement dans celui-ci. Dès qu’un appel plus profond signale un cycle, propagez la valeur vraie vers le haut.
elif color[v] == WHITE and dfs(v):
return TrueLe noir est sûr
Un voisin noir a été entièrement exploré et ne contient aucun cycle : vous pouvez donc l’ignorer. Le visiter à nouveau ne ferait que perdre du temps.
Terminer un nœud
Après avoir traité tous les voisins, colorez le nœud en noir. Il quitte le chemin actif et est marqué comme terminé.
color[u] = BLACK
return FalseCouvrir chaque composante
Le graphe peut être déconnecté : lancez donc DFS depuis chaque nœud encore blanc afin de vérifier l’ensemble du graphe.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Attention à la limite de récursion
Les graphes profonds peuvent faire déborder la pile de récursion de Python. Augmentez la limite ou réécrivez DFS avec une pile explicite.
import sys
sys.setrecursionlimit(300000)Vérification rapide
Pendant DFS, vous atteignez un voisin qui est actuellement gris. Que venez-vous de trouver ?
Récapitulatif : détection des cycles
Colorez les nœuds en blanc, puis en gris et enfin en noir. Un voisin gris pendant DFS est une arête de retour, ce qui prouve l’existence d’un cycle orienté. 🔁
Questions Fréquemment Posées
La leçon « Détecter les cycles dans les graphes orientés » est-elle gratuite ?
Oui — le texte complet de « Détecter les cycles dans les graphes orientés » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Détecter les cycles dans les graphes orientés » ?
Colorer les nœuds pour trouver les arêtes de retour Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Détecter les cycles dans les graphes orientés » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Tri topologique avec l’algorithme de Kahn
- Détecter les cycles dans les graphes orientés
- Composantes fortement connexes
- Ponts et points d’articulation