Detección de ciclos en un grafo
Detectar ciclos en grafos es fundamental para comprender la estructura y las propiedades de los datos en diversos ámbitos, como la gestión de dependencias, la detección de interbloqueos y el enrutamiento de redes. Al identificar ciclos, podemos evitar problemas como dependencias circulares, ineficiencias e incluso fallas en el sistema.
Podemos utilizar una versión modificada de DFS (búsqueda en profundidad) para detectar un ciclo en un grafo.
Al recorrer un grafo con DFS, normalmente marcamos los vértices como visitados o no visitados. Sin embargo, para detectar ciclos, esto no es suficiente. Necesitamos mantener 3 estados para cada vértice:
- Vértice no visitado
- Vértice y su subárbol DFS están en proceso
- Vértice completamente visitado (incluyendo todos sus nodos hijos)
De esta manera, podemos detectar un ciclo si, durante el recorrido, llegamos a un vértice que se encuentra en proceso.
➰
Si, al recorrer el grafo, llegamos a un vértice marcado como en proceso (2), entonces hemos encontrado un ciclo.
El algoritmo realiza los siguientes pasos:
- Marca todos los vértices como no visitados
- Inicia una DFS desde algún vértice
- Para el vértice actual, márcalo como "en proceso"
- Cuando se hayan procesado todos los nodos hijo del vértice actual, márcalo como completamente visitado
El algoritmo se puede aplicar tanto a grafos dirigidos como a grafos no dirigidos:
color = [1] * n # color de los vértices (1: no visitado, 2: en proceso, 3: completamente visitado)
def dfs(v, p): # búsqueda en profundidad (v: vértice, p: padre)
color[v] = 2 # marcar el vértice como en proceso
cycle = False # bandera para comprobar si existe un ciclo
for to in g[v]: # para cada vértice conectado a v
if color[to] == 1: # si el vértice no está visitado
cycle |= dfs(to, v) # llama a dfs en el vértice y marca si hay ciclo
elif color[to] == 2 and to != p: # si el vértice está en proceso y no es el padre
cycle = True # marca la bandera como True
color[v] = 3 # marcar el vértice como completamente visitado
return cycle # devolver la bandera
for start in range(n): # para cada vértice
if color[start] == 1: # si el vértice no está visitado
if dfs(start, -1): # llama a dfs en el vértice y comprueba si hay ciclo
print('Cycle') # imprimir "Cycle"
break # salir del bucle
else: # si el bucle no se rompe
print('No cycle') # imprimir "No cycle"Ten en cuenta que, en grafos dirigidos, no es necesario tener en cuenta el vértice padre. ¿Puedes explicar por qué 🤔?
Vamos a simular el algoritmo en varios conjuntos de datos de entrada:
n = 4, e = 4
La entrada de pares "a, b" es: [(0, 1), (0, 2), (1, 2), (3, 2)]
El vértice inicial es 3
v=3, p=-1→color = [1, 1, 1, 2]⇒ explora todos los vecinos de 3 ⇒[2]
v=2, p=3→color = [1, 1, 2, 2]⇒ explora todos los vecinos de 2 ⇒[0, 1]
v=0, p=2→color = [2, 1, 2, 2]⇒ explora todos los vecinos de 0 ⇒[1, 2]
v=1, p=0→color = [2, 2, 2, 2]⇒ explora todos los vecinos de 1 ⇒[0, 2]⇒ 0 está marcado como 1 ⇒ marcacycle = True⇒return True
Desafío: Comprobar si un grafo contiene un ciclo
Dado un grafo dirigido con v vértices y e aristas, se pide verificar si el grafo contiene un ciclo.
Entrada
La primera línea de la entrada contiene dos números enteros v (1 ≤ v ≤ 100 000) y e (1 ≤ e ≤ 100 000).
Las siguientes e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v) que indican que existe un camino desde el vértice v1 hasta el vértice v2.
Salida
El programa debe imprimir Yes si el grafo tiene un ciclo y No en caso contrario.
Ejemplos
Entrada | Salida |
4 3
1 2
2 3
3 1
| Yes |
4 3
1 2
1 3
2 4 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB