Detección de ciclos en grafos dirigidos y no dirigidos
Detecte ciclos en grafos no dirigidos mediante el seguimiento de padres y en grafos dirigidos mediante codificación de colores DFS —visitados en tres estados: blanco, gris y negro—.
Detección de ciclos en grafos dirigidos y no dirigidos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 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 Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Por qué es importante detectar ciclos
Un ciclo en un grafo es un camino que comienza y termina en el mismo nodo. La detección de ciclos es fundamental en muchos algoritmos: la ordenación topológica falla en grafos cíclicos, la resolución de dependencias debe detectar dependencias circulares y la detección de interbloqueos en la planificación del sistema operativo requiere encontrar ciclos en grafos de asignación de recursos. El enfoque difiere entre grafos no dirigidos y dirigidos: requieren algoritmos fundamentalmente distintos.
from collections import defaultdict
# Undirected cycle: A-B-C-A (triangle)
undirected = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
undirected[u].append(v)
undirected[v].append(u)
# Directed cycle: A->B->C->A
directed = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
directed[u].append(v) # one direction only
# Key difference:
# Undirected: edge A-B appears as both A->B and B->A
# Must track parent to distinguish cycle from back-edge to parent
print('Undirected and directed cycles need different detection')Detección de ciclos en grafos no dirigidos con DFS
En un grafo no dirigido, existe un ciclo si el DFS visita un nodo que ya está en el camino actual (no basta con que esté visitado). El desafío es que cada arista aparece en ambas direcciones, por lo que, al visitar un nodo hijo, su lista de vecinos incluye el nodo actual (el padre). Debemos realizar un seguimiento del padre de cada nodo para evitar marcar falsamente como ciclo la arista que regresa al padre. Si encontramos un nodo visitado que no es nuestro padre, hemos encontrado un ciclo.
def has_cycle_undirected(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
if dfs(nb, node): # recurse with current as parent
return True
elif nb != parent: # visited and not parent = CYCLE
return True
return False
for node in range(n):
if node not in visited:
if dfs(node, -1): # -1 = no parent for root
return True
return False
print(has_cycle_undirected(4, [(0,1),(1,2),(2,3),(3,1)])) # True
print(has_cycle_undirected(3, [(0,1),(1,2)])) # FalseCiclos en grafos no dirigidos con BFS
La detección de ciclos mediante BFS en un grafo no dirigido también realiza un seguimiento del padre de cada nodo visitado. Al procesar los vecinos de un nodo, si un vecino ya está visitado y no es el padre del nodo actual, existe un ciclo. Use un diccionario para almacenar los padres. Este enfoque O(V + E) evita el problema del límite de recursión y es la alternativa iterativa preferida para grafos grandes.
from collections import deque, defaultdict
def has_cycle_bfs_undirected(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
for start in range(n):
if start in visited:
continue
visited.add(start)
parent = {start: -1}
queue = deque([start])
while queue:
node = queue.popleft()
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
parent[nb] = node
queue.append(nb)
elif parent[node] != nb: # visited and not parent = CYCLE
return True
return False
print(has_cycle_bfs_undirected(4, [(0,1),(1,2),(2,0)])) # TrueCiclos dirigidos: por qué falla el seguimiento del padre
En un grafo dirigido, realizar un seguimiento del padre no es suficiente. Considere A→C y B→C: el nodo C tiene dos «padres», pero no hay ningún ciclo. El enfoque correcto utiliza un coloreado de tres estados: blanco (no visitado), gris (en el camino o la pila DFS actual) y negro (procesado por completo). Existe un ciclo si durante el DFS encontramos un nodo gris, lo que significa que hemos encontrado una arista de retorno hacia un ancestro del camino actual.
# Three-state DFS coloring:
# WHITE (0): not yet visited
# GRAY (1): currently being visited (in DFS stack)
# BLACK (2): fully visited (all descendants processed)
# Why parent fails for directed graphs:
# A -> C (no cycle)
# B -> C (no cycle)
# If we DFS from A, mark C gray
# Then DFS from B finds C is gray -- but this is NOT a cycle!
# C is gray from A's path, not B's path.
# Parent tracking only works when the back-edge goes to the IMMEDIATE parent.
print('Directed graph: use 3-state coloring (white/gray/black)')Detección de ciclos dirigidos con DFS de tres estados
Use un arreglo state[] con los valores 0 (blanco/no visitado), 1 (gris/en la pila) y 2 (negro/terminado). Inicie el DFS, marcando el nodo como gris al entrar y como negro al salir. Si el DFS llega alguna vez a un nodo gris, se ha encontrado una arista de retorno y existe un ciclo. Si llega a un nodo negro, esa ruta ya se exploró por completo y no contiene ciclos, así que debe omitirla.
def has_cycle_directed(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
state = [0] * n # 0=white, 1=gray, 2=black
def dfs(node):
state[node] = 1 # mark gray (in stack)
for nb in graph[node]:
if state[nb] == 1: # gray = back edge = CYCLE
return True
if state[nb] == 0: # white = unvisited
if dfs(nb):
return True
state[node] = 2 # mark black (fully processed)
return False
for node in range(n):
if state[node] == 0:
if dfs(node):
return True
return False
print(has_cycle_directed(4, [(0,1),(1,2),(2,0),(2,3)])) # True (0->1->2->0)
print(has_cycle_directed(3, [(0,1),(1,2)])) # FalsePlanificación de cursos: ciclo en un DAG
Planificación de cursos (LeetCode #207) pregunta si se pueden terminar todos los cursos dadas sus prerrequisitos. Modele los cursos como nodos y los prerrequisitos como aristas dirigidas. Se pueden terminar todos los cursos si y solo si el grafo es un DAG (sin ciclos). Use la detección de ciclos mediante DFS de tres estados: si se encuentra un ciclo, devuelva False; de lo contrario, devuelva True.
from collections import defaultdict
def can_finish(num_courses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a) # b is prerequisite for a: b -> a
state = [0] * num_courses
def dfs(course):
if state[course] == 1: return False # cycle!
if state[course] == 2: return True # already verified
state[course] = 1 # mark as in-progress
for next_course in graph[course]:
if not dfs(next_course):
return False
state[course] = 2 # mark as done
return True
return all(dfs(i) for i in range(num_courses) if state[i] == 0)
print(can_finish(2, [[1,0]])) # True: take 0 then 1
print(can_finish(2, [[1,0],[0,1]])) # False: circular dependencyDetección de ciclos con el algoritmo de Kahn (BFS)
Una alternativa para detectar ciclos en grafos dirigidos utiliza la ordenación topológica BFS de Kahn. Cuente los grados de entrada de todos los nodos. Coloque en una cola los nodos cuyo grado de entrada sea 0. Procese cada uno: reduzca los grados de entrada de sus vecinos y añada a la cola los que lleguen a 0. Si el número de nodos procesados es igual a V, no hay ningún ciclo; de lo contrario, existe un ciclo (los nodos no procesados forman ciclos). Este enfoque O(V + E) es intuitivo y más fácil de recordar que el DFS de tres estados.
from collections import defaultdict, deque
def has_cycle_kahn(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
# Start with all zero in-degree nodes
queue = deque(i for i in range(n) if in_degree[i] == 0)
processed = 0
while queue:
node = queue.popleft()
processed += 1
for nb in graph[node]:
in_degree[nb] -= 1
if in_degree[nb] == 0:
queue.append(nb)
return processed != n # if not all processed, cycle exists
print(has_cycle_kahn(4, [(0,1),(1,2),(2,0),(2,3)])) # True
print(has_cycle_kahn(3, [(0,1),(1,2)])) # FalseEncontrar el ciclo: recopilar los nodos del ciclo
A veces necesita identificar qué nodos forman parte de un ciclo, no solo detectar si existe. Durante un DFS de tres estados, cuando se encuentra una arista de retorno, recorra hacia atrás la pila de llamadas (o una pila de caminos) para recopilar todos los nodos entre el ancestro y el nodo actual. Una pila de caminos mantenida junto al arreglo de estados captura el camino DFS actual y permite reconstruir el ciclo en O(longitud_del_ciclo).
def find_cycle_nodes(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
state = [0] * n
path = [] # current DFS path
cycle = []
def dfs(node):
state[node] = 1
path.append(node)
for nb in graph[node]:
if state[nb] == 1: # back edge -> found cycle
start = path.index(nb)
cycle.extend(path[start:])
return True
if state[nb] == 0 and dfs(nb):
return True
path.pop()
state[node] = 2
return False
for i in range(n):
if state[i] == 0 and dfs(i):
break
return cycle
print(find_cycle_nodes(4, [(0,1),(1,2),(2,0),(2,3)])) # [0, 1, 2]Encontrar estados eventualmente seguros
Encontrar estados eventualmente seguros (LeetCode #802) pregunta qué nodos conducen finalmente a un nodo terminal (sin aristas salientes) sin quedar atrapados en un ciclo. Un nodo es «seguro» si todos los caminos que parten de él conducen a nodos terminales. Use un DFS de tres estados: los nodos negros (procesados por completo sin detectar ciclos) son seguros. Los nodos que forman parte de un ciclo o conducen a él no son seguros.
def eventual_safe_nodes(graph):
n = len(graph)
state = [0] * n # 0=unvisited, 1=visiting, 2=safe
def dfs(node):
if state[node] == 1: # currently visiting = cycle
return False
if state[node] == 2: # already verified safe
return True
state[node] = 1 # mark as visiting
for nb in graph[node]:
if not dfs(nb):
return False # leads to cycle, not safe
state[node] = 2 # mark as safe
return True
return [i for i in range(n) if dfs(i)]
# [[1,2],[2,3],[5],[0],[5],[],[]] means:
# 0->[1,2], 1->[2,3], 2->[5], 3->[0] (cycle!), 4->[5], 5->[], 6->[]
print(eventual_safe_nodes([[1,2],[2,3],[5],[0],[5],[],[]]))
# [2, 4, 5, 6]Conexión redundante en un grafo no dirigido
Conexión redundante (LeetCode #684) encuentra la arista que crea un ciclo al añadirse a un grafo no dirigido que, por lo demás, no contiene ciclos. Aunque puede resolverse mediante la detección de ciclos con DFS, la solución más clara utiliza Union-Find (DSU): procese las aristas una por una; si ambos extremos ya están conectados (pertenecen al mismo componente), la arista actual crea un ciclo y es la respuesta. DSU ofrece O(alpha(n)) por operación, lo que equivale prácticamente a O(1).
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # already connected = cycle!
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v] # this edge creates the cycle
return []
print(find_redundant_connection([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]])) # [1,4]Resumen: estrategias de detección de ciclos
Para resumir las herramientas de detección de ciclos: para grafos no dirigidos, use DFS con seguimiento del padre o Union-Find. Para grafos dirigidos, use DFS de tres estados (blanco/gris/negro) o la ordenación topológica BFS de Kahn. Elija Union-Find cuando añada aristas una por una (en línea). Elija Kahn cuando también necesite el orden topológico. Elija DFS de tres estados cuando necesite identificar los nodos específicos del ciclo. Al hablar de detección de ciclos en entrevistas, indique siempre la diferencia entre grafos dirigidos y no dirigidos.
# Cycle detection summary:
# Graph type | Algorithm | Complexity
# ------------|----------------------|-----------
# Undirected | DFS + parent track | O(V + E)
# Undirected | Union-Find (DSU) | O(E * alpha(V))
# Directed | DFS 3-state (W/G/B) | O(V + E)
# Directed | Kahn's BFS topo sort | O(V + E)
# When to choose:
# Online (edges added one at a time): Union-Find
# Need topological order too: Kahn's BFS
# Need cycle nodes identified: 3-state DFS with path stack
# Simple existence check: any of the above
print('Always clarify directed vs undirected before coding')Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Repaso de la lección
En esta lección ha aprendido: la detección de ciclos no dirigidos con DFS y seguimiento del padre, la detección de ciclos dirigidos con coloreado de tres estados blanco/gris/negro, la alternativa BFS de Kahn para grafos dirigidos y aplicaciones como la planificación de cursos, la conexión redundante y los estados eventualmente seguros. A continuación nos adentraremos en los fundamentos de la programación dinámica.
Preguntas frecuentes
¿La lección «Detección de ciclos en grafos dirigidos y no dirigidos» es gratis?
Sí — el texto completo de «Detección de ciclos en grafos dirigidos y no 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 Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Detección de ciclos en grafos dirigidos y no dirigidos»?
Detecte ciclos en grafos no dirigidos mediante el seguimiento de padres y en grafos dirigidos mediante codificación de colores DFS —visitados en tres estados: blanco, gris y negro—. Practicas Coding Interview Prep 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 Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep 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 4 de 4.
¿Cuánto tiempo toma la lección «Detección de ciclos en grafos dirigidos y no 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 Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep 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
- Representaciones de grafos y preparación de recorridos
- BFS: ruta más corta y recorrido por niveles
- DFS: componentes conexos y flood fill
- Detección de ciclos en grafos dirigidos y no dirigidos