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.

How to spot this pattern

Kahn's algorithm answers two questions at once: it produces a topological order, and it detects cycles by failing to consume every vertex. Peel vertices with in-degree 0, decrement their neighbours, repeat. If the process stalls with vertices left over, those vertices are mutually dependent — a cycle.

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

▶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

Common pitfalls

Counting out-degree instead of in-degree

✗ Wrong

for u in range(n):
    indeg[u] = len(adj[u])

✓ Right

for u in range(n):
    for v in adj[u]:
        indeg[v] += 1

The queue must start with vertices that nothing points at, which is an in-degree count. Out-degree measures the opposite direction and seeds the queue with sinks, so the peeling stalls immediately.

Enqueuing a neighbour before its in-degree hits zero

✗ Wrong

for u in adj[v]:
    indeg[u] -= 1
    q.append(u)

✓ Right

for u in adj[v]:
    indeg[u] -= 1
    if indeg[u] == 0:
        q.append(u)

A vertex with several prerequisites would be processed before the rest are removed, so it's counted multiple times and removed overshoots — a cyclic graph then looks acyclic. Only a vertex with no remaining dependencies is ready.

Testing emptiness of the queue rather than the count

✗ Wrong

return not q

✓ Right

return removed < n

The queue is always empty when the loop exits — that's the loop condition. What distinguishes a cycle is how many vertices were peeled before it emptied.

06

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.

07

Complexity

Time

O(V + E)

Space

O(V)

Identical cost to a topological sort.