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
V | edges | Output | Why |
---|---|---|---|
4 | [(0,1),(1,2),(2,0),(2,3)] | True | 0 → 1 → 2 → 0 forms a loop |
3 | [(0,1),(1,2)] | False | No edge leads back to an earlier node |
1 | [(0,0)] | True | Self-loop counts as a cycle |
Intuition & Approach
We use Kahn’s algorithm, which is really a breadth-first topological sort:
- Indegree count
For every vertex count incoming edges. Nodes with indegree 0 have no prerequisites. - Queue of ready nodes
Put all indegree-0 nodes into a queue. - 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. - Cycle check
If we can remove (process) allV
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
- Graph build –
adj_list[u]
stores outgoing edges;indegrees[v]
counts incoming edges. - Initial queue – all nodes with indegree 0 have no dependencies, so they can be deleted first.
- BFS loop – for each popped node we “delete” its edges by lowering neighbours’ indegrees.
- Cycle decision –
- If
result
length equalsV
, every node was deletable → no cycle. - Otherwise at least one node stayed stuck with positive indegree, proving a cycle.
- If
Dry run on the first example
V = 4
, edges = [(0,1),(1,2),(2,0),(2,3)]
Step | Queue | result | Key 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
Measure | Value |
---|---|
Time | O(V + E) |
Space | O(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.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.