See how to solve “detect cycle in a directed graph” using depth-first search and two helper arrays. Simple idea, commented Python code, dry run, and Big-O analysis.
What does the problem ask?
You are given a directed graph with V
vertices (0 … V-1
) and a list of edges.
Return True
if the graph contains at least one directed cycle; otherwise return False
. geeksforgeeks.org
Examples
V | edges | Result | Why |
---|---|---|---|
4 | [(0,1),(1,2),(2,0),(2,3)] | True | 0 → 1 → 2 → 0 forms a cycle |
3 | [(0,1),(1,2)] | False | No path returns to an earlier node |
1 | [(0,0)] | True | Self-loop is a cycle |
Intuition & Approach
Key idea
While doing DFS, a back edge (an edge to a node already in the current recursion path) means a cycle.
How we detect that
We keep two arrays:
visited[]
– 1 if the node has been processed completely.path_visited[]
– 1 if the node is in the current DFS path (the “gray” state).
Steps:
- Start DFS from every unvisited node (graph may be disconnected).
- When we enter a node, mark both
visited
andpath_visited
. - For every neighbor:
- If neighbor is unvisited → DFS deeper.
- If neighbor is already in
path_visited
→ we met a gray node → cycle found.
- When we leave the node, clear its
path_visited
flag (turn it “black”). - If no back edge seen in any component, the graph is acyclic.
This is the classic “white-gray-black” DFS cycle test.
Code
class Solution:
# DFS that returns True as soon as a cycle is detected
def dfs(self, current_node, visited, path_visited, adj_list):
visited[current_node] = 1 # mark as visited (gray → black later)
path_visited[current_node] = 1 # mark as part of current path (gray)
for adjNode in adj_list[current_node]: # explore all outgoing edges
if visited[adjNode] == 0: # white node
x = self.dfs(adjNode, visited, path_visited, adj_list)
if x == True: # cycle found deeper
return True
elif path_visited[adjNode] == 1: # edge to gray node → cycle
return True
path_visited[current_node] = 0 # leave path (node becomes black)
return False
def isCycle(self, V, edges):
# build adjacency list
adj_list = [[] for _ in range(V)]
for u, v in edges: # edge u → v
adj_list[u].append(v)
visited = [0] * V # 0 = white (not visited at all)
path_visited = [0] * V # 0 = not in current DFS call stack
for i in range(V): # handle all components
if visited[i] == 0:
ans = self.dfs(i, visited, path_visited, adj_list)
if ans == True:
return True # cycle exists
return False # no cycles anywhere
5 Code walkthrough
- Adjacency list quickly lists every node’s outgoing edges.
dfs
marks a node gray (visited=1
,path_visited=1
).- For each neighbor:
- If neighbor is white → recurse.
- If neighbor is gray (
path_visited=1
) → back edge found → cycle.
- Once all neighbors are processed, node turns black (
path_visited=0
). - Outer loop makes sure we check every disconnected part.
- First time
True
comes back, we exit early.
6 Dry run on sample with a cycle
V = 4
, edges = [(0,1),(1,2),(2,0),(2,3)]
Call stack | visited | path_visited | Note |
---|---|---|---|
dfs(0) | [1,0,0,0] | [1,0,0,0] | node 0 gray |
→ dfs(1) | [1,1,0,0] | [1,1,0,0] | node 1 gray |
→ dfs(2) | [1,1,1,0] | [1,1,1,0] | node 2 gray |
→ neighbor 0 is gray | back edge → return True up the stack | ||
Propagate True → isCycle returns True |
7 Complexity
Measure | Value |
---|---|
Time | O(V + E) |
Space | O(V + E) |
We visit every vertex and edge once; we store the graph plus two arrays of size V
.
8 Conclusion
Using DFS with a “currently in path” marker lets us spot a back edge—the reliable sign of a directed cycle. The method is linear, easy to code, and works for any directed graph.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.