Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Detect Cycle in a Directed Graph
    Data Structures & Algorithms

    Detect Cycle in a Directed Graph

    codeanddebugBy codeanddebug3 June 2025No Comments3 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured Image of a question to how to detect a cycle in a directed graph
    Share
    Facebook Twitter LinkedIn Pinterest Email

    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

    VedgesResultWhy
    4[(0,1),(1,2),(2,0),(2,3)]True0 → 1 → 2 → 0 forms a cycle
    3[(0,1),(1,2)]FalseNo path returns to an earlier node
    1[(0,0)]TrueSelf-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:

    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)]

    Call stackvisitedpath_visitedNote
    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 grayback edge → return True up the stack
    Propagate True → isCycle returns True

    7 Complexity

    MeasureValue
    TimeO(V + E)
    SpaceO(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.

    Join our FREE Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    DFS Graph Medium
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleTopological Sort in Graph | Simple DFS + Stack Solution in Python
    Next Article Topological Sort (Kahn’s Algorithm) – Simple BFS Solution in Python
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Detect Cycle in a Directed Graph – Kahn’s Algorithm (BFS Topological Check) in Python

    4 June 2025
    Data Structures & Algorithms

    Topological Sort (Kahn’s Algorithm) – Simple BFS Solution in Python

    4 June 2025
    Data Structures & Algorithms

    Topological Sort in Graph | Simple DFS + Stack Solution in Python

    3 June 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (38)
      • Beginner (17)
      • Expert (7)
      • Intermediate (14)
    • Uncategorised (1)
    Recent Posts

    Detect Cycle in a Directed Graph – Kahn’s Algorithm (BFS Topological Check) in Python

    4 June 2025

    Topological Sort (Kahn’s Algorithm) – Simple BFS Solution in Python

    4 June 2025

    Detect Cycle in a Directed Graph

    3 June 2025

    Topological Sort in Graph | Simple DFS + Stack Solution in Python

    3 June 2025

    Is Graph Bipartite? | Leetcode 785 | Easy 2-Color DFS Solution in Python

    1 June 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.