Detect Cycle in a Directed Graph

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

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:

1. Start DFS from every unvisited node (graph may be disconnected).
2. When we enter a node, mark both visited and path_visited.
3. For every neighbor:
   • If neighbor is unvisited → DFS deeper.
   • If neighbor is already in path_visited → we met a gray node → cycle found.
4. When we leave the node, clear its path_visited flag (turn it “black”).
5. 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

1. Adjacency list quickly lists every node’s outgoing edges.
2. dfs marks a node gray (visited=1, path_visited=1).
3. For each neighbor:
   • If neighbor is white → recurse.
   • If neighbor is gray (path_visited=1) → back edge found → cycle.
4. Once all neighbors are processed, node turns black (path_visited=0).
5. Outer loop makes sure we check every disconnected part.
6. 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)]

7 Complexity

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.