Detecte ciclos en grafos dirigidos
Coloree nodos para encontrar aristas de retorno
Detecte ciclos en grafos dirigidos es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Por qué importan los ciclos
Un ciclo dirigido significa que las dependencias vuelven sobre sí mismas. Detectarlo indica que no puede existir ningún orden topológico ni una planificación válida.
Los grafos no dirigidos son diferentes
Aquí, la detección de ciclos depende de la dirección. Seguir las aristas en el sentido incorrecto no cuenta, así que no se pueden aplicar los trucos de los grafos no dirigidos.
La idea de los tres colores
Asigne a cada nodo uno de tres colores: blanco significa no visitado, gris significa en proceso y negro significa completamente procesado.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nGris significa que está en la pila
Un nodo gris se encuentra en el camino actual de DFS. Ha entrado en él, pero todavía no ha terminado de explorar todos sus descendientes.
Entrar en un nodo
Cuando DFS llega a un nodo, márquelo de gris antes de explorarlo. Así indica que forma parte del camino activo.
def dfs(u):
color[u] = GRAYLa señal de la arista de retorno
Si llega a un vecino que ya está gris, ha encontrado una arista de retorno hacia el camino actual. Eso es un ciclo.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleRecurrir en los nodos blancos
Un vecino blanco aún no se ha visitado, así que recurra en él. Devuelva True en cuanto cualquier llamada más profunda informe de un ciclo.
elif color[v] == WHITE and dfs(v):
return TrueEl negro es seguro
Un vecino negro ya se ha explorado por completo y no contiene ciclos, así que puede ignorarlo. Volver a visitarlo solo haría perder tiempo.
Terminar un nodo
Después de procesar todos los vecinos, marque el nodo de negro. Sale del camino activo y queda marcado como completo.
color[u] = BLACK
return FalseCubrir todos los componentes
El grafo puede estar desconectado, así que inicie DFS desde cada nodo que siga siendo blanco para asegurarse de comprobarlo por completo.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Tener en cuenta el límite de recursión
Los grafos profundos pueden desbordar la pila de recursión de Python. Aumente el límite o reescriba DFS con una pila explícita.
import sys
sys.setrecursionlimit(300000)Comprobación rápida
Durante DFS llega a un vecino que está actualmente gris. ¿Qué acaba de encontrar?
Repaso: detección de ciclos
Coloree los nodos de blanco, gris y después negro. Un vecino gris durante DFS es una arista de retorno, lo que demuestra que existe un ciclo dirigido. 🔁
Aprende Python con un tutor de IA — gratis
Escribe y ejecuta código real en tu navegador, obtén ayuda instantánea de un tutor de IA disponible 24/7 y continúa donde lo dejaste en la web o en la aplicación.
- Cursos
- 30
- Lecciones
- 120
Preguntas frecuentes
¿La lección «Detecte ciclos en grafos dirigidos» es gratis?
Sí — el texto completo de «Detecte ciclos en grafos dirigidos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Detecte ciclos en grafos dirigidos»?
Coloree nodos para encontrar aristas de retorno Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Detecte ciclos en grafos dirigidos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Ordenación topológica con el algoritmo de Kahn
- Detecte ciclos en grafos dirigidos
- Componentes fuertemente conexas
- Puentes y puntos de articulación