Detecting Cycles in a Graph
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
a, bpairs are the following: [(0, 1), (0, 2), (1, 2), (3, 2)]
The starting vertex is 3
color = [1, 1, 1, 2]⇒ explore all the neighbors of 3 ⇒
color = [1, 1, 2, 2]⇒ explore all the neighbors of 2 ⇒
color = [2, 1, 2, 2]⇒ explore all the neighbors of 0 ⇒
color = [2, 2, 2, 2]⇒ explore all the neighbors of 1 ⇒
[0, 2]⇒ 0 is marked as 1 ⇒ mark
cycle = True⇒
Challenge: Check if a graph contains a cycle
Given a directed graph with
eedges, 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).
elines contain pairs of integers
v2(1 ≤ v1, v2 ≤ v) which means that there is a path from vertex
v1to the vertex
The program should print
Yesif the graph has a cycle and
4 3 1 2 2 3 3 1
4 3 1 2 1 3 2 4
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB