Detección de Ciclos en un Grafo

Pseudocódigo

Los grafos dirigidos y no dirigidos necesitan pruebas realmente distintas. La versión dirigida sigue la pila de recursión; la no dirigida sigue al padre.

// Dirigido: DFS de tres colores
BLANCO = no visitado, GRIS = en la pila, NEGRO = terminado

tieneCiclo(u):
    color[u] = GRIS
    para cada vecino v de u:
        si color[v] == GRIS: devolver verdadero   // retroceso
        si color[v] == BLANCO y tieneCiclo(v):
            devolver verdadero
    color[u] = NEGRO
    devolver falso

// No dirigido: DFS que arrastra el padre
tieneCiclo(u, padre):
    visitados.añadir(u)
    para cada vecino v de u:
        si v == padre: continuar
        si v en visitados: devolver verdadero
        si tieneCiclo(v, u): devolver verdadero
    devolver falso

La distinción importa más de lo que parece. En un grafo dirigido, alcanzar un nodo NEGRO es una arista cruzada y está perfectamente libre de ciclos, así que la comprobación ingenua de visitados informa de ciclos que no existen. En un grafo no dirigido, omitir al padre es lo que impide que cada arista se lea como un ciclo de dos nodos.

Ejemplo resuelto, paso a paso

Ejecuta la prueba dirigida de tres colores sobre un grafo que contiene un ciclo y una arista cruzada engañosa.

Grafo de ejemplo: Aristas dirigidas A a B, A a C, B a D, C a D y D a B.

1. Entrar en A. color[A] = GRIS. Toma el primer vecino, B.
2. Entrar en B. color[B] = GRIS. Su único vecino es D.
3. Entrar en D. color[D] = GRIS. Su vecino es B, y color[B] es GRIS. B está en la pila de recursión actual, así que D a B es una arista de retroceso y queda confirmado el ciclo B a D a B.
4. Qué haría la versión ingenua. Supón que no existiera la arista D a B. D terminaría en NEGRO, el control volvería a A, y A a C a D encontraría D ya visitado. Una comprobación simple de visitados lo llamaría ciclo. No lo es: es una arista cruzada hacia un subárbol terminado, y la prueba de tres colores la ignora correctamente porque D es NEGRO, no GRIS.

El grafo sí contiene un ciclo, B a D a B, hallado mediante la prueba GRIS. El camino A a C a D no es un ciclo, y solo la distinción de colores separa ambos casos.

Complejidad y de dónde sale

Tiempo: O(V + E) · Espacio: O(V)

Ambas variantes son un único DFS con trabajo extra constante por arista, así que el coste es el del recorrido. El vector de colores o el conjunto de visitados es O(V), más O(V) de pila de recursión. La alternativa con Union-Find para grafos no dirigidos corre en O(E alfa(V)), efectivamente lineal, y es preferible cuando las aristas llegan de una en una y quieres rechazar la arista que cierra el ciclo en el momento en que aparece, sin volver a recorrer el grafo entero.

Cuándo usar Detección de Ciclos y cuándo no

Elige la prueba que corresponda tanto a la dirección de tus aristas como a si el grafo es estático o llega por partes.

Errores frecuentes

• Usar la prueba no dirigida en un grafo dirigido. Este es el fallo más común en detección de ciclos. Una comprobación simple de visitados en un grafo dirigido informa de un ciclo por cualquier arista cruzada hacia un subárbol ya terminado. Usa tres colores, o lleva la pila de recursión como conjunto aparte.
• Olvidar reiniciar la marca de la pila de recursión. La marca GRIS debe pasar a NEGRO cuando el nodo termina. Dejar nodos en GRIS hace que todo camino posterior hacia ellos parezca una arista de retroceso, lo que produce falsos positivos en la segunda raíz del DFS y siguientes.
• No reiniciar en componentes desconectadas. Un DFS desde un origen solo ve una componente. El ciclo puede estar en una componente en la que nunca entraste, así que recorre todos los vértices y arranca un DFS nuevo desde cada uno que siga sin visitar.
• Bucles propios y aristas paralelas. Un bucle propio es un ciclo de longitud uno y la comprobación del padre no lo detecta. Dos aristas paralelas entre el mismo par forman un ciclo de longitud dos en un multigrafo no dirigido, pero omitir al padre sin condiciones lo oculta. Omite la arista del padre una vez, no todas sus apariciones.

Preguntas frecuentes

¿Cómo se detecta un ciclo en un grafo dirigido?

Ejecuta un DFS que coloree los nodos de blanco, gris y negro. Un nodo está gris mientras permanece en la pila de recursión actual y pasa a negro al terminar. Una arista hacia un nodo gris es una arista de retroceso y demuestra un ciclo. Una arista hacia un nodo negro es cruzada o de avance y no demuestra nada. Toda la prueba es O(V + E).

¿Cómo se detecta un ciclo en un grafo no dirigido?

Ejecuta un DFS que arrastre el padre de cada nodo. Si alcanzas un nodo ya visitado que no es el padre, esa arista cierra un ciclo. Otra opción es Union-Find: procesa las aristas una a una e informa de un ciclo la primera vez que ambos extremos ya estén en el mismo conjunto.

¿Por qué falla la comprobación de visitados en grafos dirigidos?

Porque estar visitado solo significa que el nodo se alcanzó antes, no que sea antecesor del nodo actual. En el grafo A a B, A a C, B a D, C a D no hay ciclo y, sin embargo, una comprobación simple de visitados marca la arista C a D porque D ya se había visto a través de B. Necesitas saber si el destino sigue en la pila de recursión.

¿Cuál es la forma más rápida de detectar un ciclo?

Para un grafo estático, un único DFS en O(V + E) es óptimo, ya que como mínimo hay que leer la entrada. Para un grafo no dirigido que se construye arista a arista, Union-Find es mejor en la práctica porque cada arista añadida se comprueba en tiempo casi constante sin volver a recorrer nada.

¿Puede un DAG contener un ciclo?

No, por definición. Un grafo dirigido acíclico es precisamente un grafo dirigido sin ciclos, y por eso la detección de ciclos es la comprobación de validez estándar antes de ordenar topológicamente. Si existe un ciclo, no existe ninguna ordenación topológica válida.