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 – Kahn’s Algorithm (BFS Topological Check) in Python
    Data Structures & Algorithms

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

    codeanddebugBy codeanddebug4 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

    Learn how to detect cycle in a directed graph with Kahn’s algorithm. Simple intuition, commented Python code, step-by-step dry run, and clear time / space complexity.

    Here’s the [Problem Link] to begin with.

    Contents:
     [show]
    • What does the problem ask?
    • Examples
    • Intuition & Approach
    • Code
    • Code walkthrough
    • Dry run on the first example
    • Complexity
    • Conclusion

    What does the problem ask?

    Given a directed graph with V vertices (0 … V-1) and a list of directed edges, tell whether the graph contains at least one cycle.
    Return True if a cycle exists; otherwise return False.


    Examples

    VedgesOutputWhy
    4[(0,1),(1,2),(2,0),(2,3)]True0 → 1 → 2 → 0 forms a loop
    3[(0,1),(1,2)]FalseNo edge leads back to an earlier node
    1[(0,0)]TrueSelf-loop counts as a cycle

    Intuition & Approach

    We use Kahn’s algorithm, which is really a breadth-first topological sort:

    1. Indegree count
      For every vertex count incoming edges. Nodes with indegree 0 have no prerequisites.
    2. Queue of ready nodes
      Put all indegree-0 nodes into a queue.
    3. Process the queue
      Repeatedly pop a node, “remove” its outgoing edges by decrementing each neighbour’s indegree.
      Whenever a neighbour’s indegree becomes 0, push it into the queue.
    4. Cycle check
      If we can remove (process) all V nodes, the graph is acyclic.
      If some nodes never reach indegree 0, they are locked in a cycle.

    So:

    • All nodes processed? → No cycle (False)
    • Some left unprocessed? → Cycle exists (True)

    Code

    from collections import deque
    
    
    class Solution:
        def isCycle(self, V, edges):
            adj_list = [[] for _ in range(V)]
            indegrees = [0 for _ in range(V)]      # incoming edge counts
    
            # Build graph and indegree array
            for u, v in edges:                     # edge u → v
                adj_list[u].append(v)
                indegrees[v] += 1
    
            queue = deque()
            result = []                            # list of processed nodes
    
            # Put all sources (indegree 0) into the queue
            for i in range(V):
                if indegrees[i] == 0:
                    queue.append(i)
    
            # Standard BFS over the DAG / graph
            while len(queue) != 0:
                current_node = queue.popleft()
                result.append(current_node)
                for adjNode in adj_list[current_node]:
                    indegrees[adjNode] -= 1        # remove edge current → adjNode
                    if indegrees[adjNode] == 0:    # neighbour becomes a new source
                        queue.append(adjNode)
    
            # If we processed every vertex, no cycle; otherwise a cycle exists
            if len(result) == V:
                return False                       # acyclic
            return True                            # cycle present

    Code walkthrough

    1. Graph build – adj_list[u] stores outgoing edges; indegrees[v] counts incoming edges.
    2. Initial queue – all nodes with indegree 0 have no dependencies, so they can be deleted first.
    3. BFS loop – for each popped node we “delete” its edges by lowering neighbours’ indegrees.
    4. Cycle decision –
      • If result length equals V, every node was deletable → no cycle.
      • Otherwise at least one node stayed stuck with positive indegree, proving a cycle.

    Dry run on the first example

    V = 4, edges = [(0,1),(1,2),(2,0),(2,3)]

    StepQueueresultKey indegree changes
    Build––indeg = [1,1,1,1]
    No node has indegree 0[][]queue empty from start
    BFS ends immediately[][]processed = 0
    processed ≠ V (0 ≠ 4) → cycle

    Algorithm returns True.


    Complexity

    MeasureValue
    TimeO(V + E)
    SpaceO(V + E)

    Conclusion

    Kahn’s algorithm offers a neat BFS way to detect cycles in directed graphs:

    • Keep indegrees.
    • Remove zero-indegree nodes layer by layer.
    • If anything remains, a cycle must be blocking progress.

    The method is linear, easy to code, and widely used in scheduling and dependency resolution tasks.

    Join our FREE Advance DSA COURSE

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

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

    Related Posts

    Data Structures & Algorithms

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

    4 June 2025
    Data Structures & Algorithms

    Detect Cycle in a Directed Graph

    3 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.