Detectar un ciclo consiste en determinar si es posible partir de un vértice, seguir las aristas y regresar al punto inicial. El método cambia según el grafo sea dirigido o no dirigido.
Un ciclo representa un recorrido cerrado. En una red de caminos puede ofrecer una ruta alternativa; en una jerarquía de dependencias puede indicar una contradicción; en un árbol, demuestra que la estructura dejó de ser acíclica.
La detección de ciclos aparece en compiladores, administradores de paquetes, sistemas de archivos, redes, planificación de tareas y validación de árboles. No existe un único procedimiento para todos los grafos: debemos considerar la dirección de las aristas y la forma en que recibimos los datos.
Un ciclo es una secuencia de vértices que comienza y termina en el mismo nodo y utiliza aristas válidas entre elementos consecutivos.
En un ciclo simple no se repiten vértices intermedios. En grafos simples no dirigidos, un ciclo utiliza al menos tres vértices. Un lazo v → v constituye por sí mismo un ciclo cuando el modelo admite lazos.
En un grafo no dirigido podemos recorrer una arista en ambos sentidos. Por eso, al usar DFS, regresar inmediatamente al padre no debe confundirse con un ciclo.
En un grafo dirigido las aristas solo pueden recorrerse en su orientación. Tener A → B y A → C no permite regresar a A; para formar un ciclo debe existir un camino dirigido que cierre la vuelta.
| Tipo de grafo | Señal durante DFS |
|---|---|
| No dirigido | Arista hacia un visitado que no es el padre |
| Dirigido | Arista hacia un vértice que continúa en la pila activa |
Al recorrer un grafo no dirigido con DFS guardamos, además del vértice actual, el nodo desde el que llegamos. Si encontramos un vecino visitado distinto del padre, existe otra ruta que conecta ambos puntos y, por lo tanto, se ha formado un ciclo.
Es necesario iniciar una búsqueda desde cada vértice todavía no visitado para cubrir grafos desconectados.
Pulsa cerca de una arista para seleccionarla o quitarla. El detector analiza cada componente del grafo no dirigido y resalta en rosa las aristas de un ciclo encontrado.
Las líneas grises son aristas disponibles, las verdes están seleccionadas y las rosas forman un ciclo detectado. Puede haber otros ciclos además del resaltado.
function tieneCicloNoDirigido(grafo) {
const visitados = new Set();
function dfs(actual, padre) {
visitados.add(actual);
for (const vecino of grafo[actual]) {
if (!visitados.has(vecino)) {
if (dfs(vecino, actual)) return true;
} else if (vecino !== padre) {
return true;
}
}
return false;
}
for (const vertice of Object.keys(grafo)) {
if (!visitados.has(vertice) && dfs(vertice, null)) {
return true;
}
}
return false;
}Supongamos que DFS recorre A — B. Desde B observa a A como vecino ya visitado, pero esa es la misma arista utilizada para llegar a B. No representa una ruta alternativa ni cierra un ciclo.
Esta regla supone un grafo simple. Si se permiten aristas paralelas entre los mismos vértices, dos aristas distintas pueden formar un ciclo de longitud dos y deben identificarse individualmente.
En un grafo dirigido no alcanza con encontrar cualquier vértice visitado. Una arista puede apuntar a un nodo terminado de otra rama sin formar un ciclo. El ciclo aparece cuando la arista vuelve hacia un vértice que todavía pertenece al camino DFS activo.
Se suelen utilizar tres colores o estados:
function tieneCicloDirigido(grafo) {
const estado = {}; // 0: blanco, 1: gris, 2: negro
function dfs(actual) {
estado[actual] = 1;
for (const vecino of grafo[actual]) {
if (estado[vecino] === 1) return true;
if (!estado[vecino] && dfs(vecino)) return true;
}
estado[actual] = 2;
return false;
}
for (const vertice of Object.keys(grafo)) {
if (!estado[vertice] && dfs(vertice)) return true;
}
return false;
}Durante DFS dirigido, las aristas pueden interpretarse según el estado del destino:
| Destino | Interpretación | ¿Prueba un ciclo? |
|---|---|---|
| Blanco | Arista de descubrimiento | No |
| Gris | Arista hacia un ancestro activo | Sí |
| Negro | Arista hacia un nodo ya terminado | No por sí sola |
Una implementación iterativa debe conservar explícitamente suficiente información para saber cuándo comienza y termina el procesamiento de cada vértice.
El algoritmo de Kahn también detecta ciclos dirigidos. Elimina sucesivamente vértices con grado de entrada cero. Si el proceso se detiene y todavía quedan vértices, estos participan en dependencias cíclicas o dependen de ellas.
Este método es conveniente cuando, además de validar el grafo, necesitamos producir un orden topológico si las dependencias son correctas.
Si las aristas de un grafo no dirigido llegan una por una, podemos usar una estructura de conjuntos disjuntos, también llamada Union-Find.
function tieneCicloUnionFind(vertices, aristas) {
const padre = Object.fromEntries(vertices.map(v => [v, v]));
const rango = Object.fromEntries(vertices.map(v => [v, 0]));
function find(x) {
if (padre[x] !== x) padre[x] = find(padre[x]);
return padre[x];
}
function union(a, b) {
let ra = find(a), rb = find(b);
if (ra === rb) return false;
if (rango[ra] < rango[rb]) [ra, rb] = [rb, ra];
padre[rb] = ra;
if (rango[ra] === rango[rb]) rango[ra]++;
return true;
}
for (const [a, b] of aristas) {
if (!union(a, b)) return true;
}
return false;
}La compresión de caminos y la unión por rango hacen que las operaciones sean casi constantes en la práctica. Este enfoque no se traslada directamente a ciclos dirigidos.
A veces no basta con responder sí o no: necesitamos mostrar la dependencia problemática. Durante DFS podemos guardar el padre de cada vértice.
Al hallar una arista hacia un ancestro, se recorre la cadena de padres desde el vértice actual hasta ese ancestro. Esa cadena, junto con la arista de retroceso, reconstruye el ciclo.
En sistemas reales conviene devolver esta secuencia para ofrecer un diagnóstico comprensible al usuario.
| Método | Tipo de grafo | Tiempo | Cuándo usarlo |
|---|---|---|---|
| DFS con padre | No dirigido | O(V + E) | Grafo completo en memoria |
| DFS con colores | Dirigido | O(V + E) | Analizar rutas y reconstruir ciclos |
| Kahn | Dirigido | O(V + E) | Validar y ordenar dependencias |
| Union-Find | No dirigido | Casi O(E) | Aristas agregadas incrementalmente |
DFS requiere O(V) de espacio adicional para visitados, padres y pila. Kahn utiliza O(V) para grados y cola. Union-Find utiliza O(V) para sus conjuntos.
Detectar ciclos permite distinguir árboles de grafos generales y validar relaciones de dependencia. La clave es respetar la naturaleza del grafo: padre en el caso no dirigido, pila activa en el dirigido y conjuntos disjuntos cuando las conexiones no dirigidas llegan incrementalmente.
En el próximo tema estudiaremos las componentes fuertemente conexas, regiones de un grafo dirigido donde todos los vértices pueden alcanzarse mutuamente.