GeeksforGeeks Medium

Detect Cycle in Directed Graph (BFS)

Detect a cycle in a directed graph using Kahn's in-degree peeling.

graphbfscyclein-degree

02

Intuition

💡

Run a topological sort and see whether it finishes. Vertices with no incoming edges can always be peeled away; each removal may free others. A vertex inside a cycle is always waiting on another vertex in that same cycle, so its in-degree never reaches zero. If the peeling ends before all V vertices are removed, whatever is left is exactly the cyclic part.

03

Approach

1

Reuse Kahn's machinery

Compute in-degrees, queue the zeros, and peel. Only the final check differs from a plain topological sort.

2

Count what came out

Track how many vertices were peeled. If that count is less than V, a cycle exists — no extra bookkeeping needed.

3

BFS vs DFS for this

Kahn's needs no recursion and no colours, which makes it the safer choice on very deep graphs; the DFS/grey version is better when you also want the actual cycle.

04

Solution & live demo

python

▶1from collections import deque
▶2 
▶3def has_cycle_directed_bfs(n, adj):
▶4    indeg = [0] * n
▶5    for u in range(n):
▶6        for v in adj[u]:
▶7            indeg[v] += 1
▶8    q = deque(v for v in range(n) if indeg[v] == 0)
▶9    removed = 0
▶10    while q:
▶11        v = q.popleft()           # in-degree 0 -> peel
▶12        removed += 1
▶13        for u in adj[v]:
▶14            indeg[u] -= 1
▶15            if indeg[u] == 0:
▶16                q.append(u)
▶17    return removed < n            # stalled early -> cycle

05

Edge cases

Pure DAG

All V vertices peel — no cycle.

Disconnected, one part cyclic

The acyclic part peels, the cyclic part stalls, count falls short.

Self-loop

That vertex's in-degree includes itself and never reaches 0.

06

Complexity

Time

O(V + E)

Space

O(V)

Identical cost to a topological sort.