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

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.

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

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

Algorithm returns True.

Complexity

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.

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