Detecting cycles in graphs is essential for understanding the structure and properties of data across various domains, such as dependency management, deadlock detection, and network routing. By identifying cycles, we can prevent issues like circular dependencies, inefficiencies, and even system failures.
A modified version of DFS can be used to detect a cycle in a graph.
When traversing a graph with DFS we usually mark vertices as visited/used or not visited. When detecting cycles, that’s not enough. We need to keep 3 states for each vertex:
Vertex is not visited
Vertex and its DFS subtree are being processed
Vertex is fully visited (with all the child nodes)
This way we can detect a cycle if we reach a vertex that is currently being processed by traversing the graph.
If we reach a vertex that is marked as being processed (2) while traversing the graph, then we have found a cycle.
The algorithm would perform the following steps:
Mark all the vertices as not visited
Start a DFS from some vertex
For the current vertex, mark it as being processed
When all the child nodes of the current vertex have been processed, mark it as fully visited
The algorithm can be applied to both directed and undirected graphs:
color =  * n # color of vertices (1: not visited, 2: being processed, 3: fully visited)
def dfs(v, p): # depth-first search (v: vertex, p: parent)
color[v] = 2 # mark vertex as being processed
cycle = False # flag to check if there is a cycle
for to in g[v]: # for each vertex connected to v
if color[to] == 1: # if vertex is not visited
cycle |= dfs(to, v) # call dfs on vertex and mark if there is a cycle
elif color[to] == 2 and to != p: # if vertex is being processed and it is not the parent
cycle = True # mark flag as True
color[v] = 3 # mark vertex as fully visited
return cycle # return flag
for start in range(n): # for each vertex
if color[start] == 1: # if vertex is not visited
if dfs(start, -1): # call dfs on vertex and check if there is a cycle
print('Cycle') # print cycle
break # break loop
else: # If the loop wasn't stopped with break
print('No cycle') # print no cycle
Note that for directed graphs, taking into account the parent vertex is not necessary. Can you tell why 🤔?
Let’s simulate the algorithm on several inputs:
n = 4, e = 4
The input a, b pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 2)]
The starting vertex is 3
v=3, p=-1 → color = [1, 1, 1, 2] ⇒ explore all the neighbors of 3 ⇒ 
v=2, p=3 → color = [1, 1, 2, 2] ⇒ explore all the neighbors of 2 ⇒ [0, 1]
v=0, p=2 → color = [2, 1, 2, 2] ⇒ explore all the neighbors of 0 ⇒ [1, 2]
v=1, p=0 → color = [2, 2, 2, 2] ⇒ explore all the neighbors of 1 ⇒ [0, 2] ⇒ 0 is marked as 1 ⇒ mark cycle = True ⇒ return True
Challenge: Check if a graph contains a cycle
Given a directed graph with v vertices and e edges, you are asked to check if the graph contains a cycle.
The first line of the input contains two integers v (1 ≤ v ≤ 100 000) and e (1 ≤ e ≤ 100 000).
The following e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that there is a path from vertex v1 to the vertex v2.
The program should print Yes if the graph has a cycle and No otherwise.