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.

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.

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] == 1, 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 C

#include <stdio.h>
#include <stdlib.h>

typedef struct Arista {
  int destino;
  struct Arista *sig;
} Arista;

typedef struct {
  int n;
  Arista **listas;
} Grafo;

int dfsNoDirigido(const Grafo *g, int u, int padre, int *visitado) {
  visitado[u] = 1;
  for (Arista *it = g->listas[u]; it; it = it->sig) {
    int v = it->destino;
    if (!visitado[v]) {
      if (dfsNoDirigido(g, v, u, visitado)) return 1;
    } else if (v != padre) {
      return 1; /* ciclo */
    }
  }
  return 0;
}

int dfsDirigido(const Grafo *g, int u, int *visitado, int *enRecursion) {
  visitado[u] = 1;
  enRecursion[u] = 1;
  for (Arista *it = g->listas[u]; it; it = it->sig) {
    int v = it->destino;
    if (!visitado[v]) {
      if (dfsDirigido(g, v, visitado, enRecursion)) return 1;
    } else if (enRecursion[v]) {
      return 1; /* back edge */
    }
  }
  enRecursion[u] = 0;
  return 0;
}

int hayCicloNoDirigido(const Grafo *g) {
  int *visitado = calloc(g->n, sizeof(int));
  int ciclo = 0;
  for (int u = 0; u < g->n && !ciclo; u++) {
    if (!visitado[u]) {
      ciclo = dfsNoDirigido(g, u, -1, visitado);
    }
  }
  free(visitado);
  return ciclo;
}

int hayCicloDirigido(const Grafo *g) {
  int *visitado = calloc(g->n, sizeof(int));
  int *enRecursion = calloc(g->n, sizeof(int));
  int ciclo = 0;
  for (int u = 0; u < g->n && !ciclo; u++) {
    if (!visitado[u]) {
      ciclo = dfsDirigido(g, u, visitado, enRecursion);
    }
  }
  free(visitado);
  free(enRecursion);
  return ciclo;
}

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.