13 - Detección de ciclos

Un ciclo ocurre cuando se regresa a un nodo por otro camino y se forma una vuelta completa. Detectar ciclos indica si un grafo puede recorrerse sin repetir aristas y es clave para tareas como ordenamiento topológico o validación de dependencias.

13.1 Ciclos en grafos no dirigidos

Un ciclo se detecta cuando en DFS encontramos un vecino ya visitado que no es el padre inmediato. Las aristas duplicadas o multigrafos requieren controles adicionales.

Abrir detector de ciclos en grafos no dirigidos

13.2 Ciclos en grafos dirigidos

En digrafos, un ciclo se produce si alcanzamos un nodo que está en la pila de recursión (en proceso). El orden de visita importa y las aristas se siguen en su dirección.

Abrir detector de ciclos en grafos dirigidos

13.3 Uso de en_recursion

El arreglo en_recursion marca los nodos actualmente en la llamada recursiva. Si en DFS llegamos a un vecino con en_recursion[v] activo, hay ciclo dirigido.

13.4 Condiciones para falsos positivos

• Contar la arista hacia el padre como ciclo en no dirigidos; se evita verificando que v != padre.
• Confundir multiaristas o lazos con ciclos si no se manejan como casos especiales.
• En digrafos, marcar visitado sin limpiar en_recursion puede ocultar ciclos posteriores.

13.5 Implementación en Python

def dfs_no_dirigido(g, u, padre, visitado):
  visitado[u] = True
  for v, _ in g[u]:
    if not visitado[v]:
      if dfs_no_dirigido(g, v, u, visitado):
        return True
    elif v != padre:
      return True
  return False

def dfs_dirigido(g, u, visitado, en_recursion):
  visitado[u] = True
  en_recursion[u] = True
  for v, _ in g[u]:
    if not visitado[v]:
      if dfs_dirigido(g, v, visitado, en_recursion):
        return True
    elif en_recursion[v]:
      return True
  en_recursion[u] = False
  return False

def hay_ciclo_no_dirigido(g):
  visitado = {v: False for v in g}
  for u in g:
    if not visitado[u]:
      if dfs_no_dirigido(g, u, None, visitado):
        return True
  return False

def hay_ciclo_dirigido(g):
  visitado = {v: False for v in g}
  en_recursion = {v: False for v in g}
  for u in g:
    if not visitado[u]:
      if dfs_dirigido(g, u, visitado, en_recursion):
        return True
  return False

13.6 Diferencias entre ciclos dirigidos y no dirigidos

• En no dirigidos, basta evitar contar la arista al padre para detectar ciclos; cualquier back-edge indica ciclo.
• En dirigidos, solo las aristas a nodos en la pila de recursión cuentan como ciclo; aristas a nodos ya finalizados no.
• El orden topológico solo existe si no hay ciclos dirigidos; los ciclos no dirigidos impiden formar un árbol libre de retornos.

13.7 Ordenamiento topológico en pocas palabras

El orden topológico es una lista lineal de los vértices de un digrafo acíclico (DAG) donde cada arista u → v respeta el orden: u va antes que v. Sirve para planificar tareas con dependencias o compilar módulos en secuencia. Solo existe si el grafo está libre de ciclos dirigidos.

Se puede obtener con DFS tomando los vértices en orden de finalización inverso, o con el algoritmo de Kahn (cola de nodos con grado de entrada cero). Si durante Kahn te quedas sin nodos y quedan aristas, hay un ciclo y el orden topológico no es posible.