Detect Cycle in Directed Graph (BFS)
Detect Cycle in a Directed Graph (BFS) is a GFG problem (Medium). You get V vertices numbered 0 … V-1 and a list edges, where edges[i] = [u, v] is a directed edge from u to v. Return true if the graph contains a cycle and false if it does not.
- A cycle follows edge directions and comes back to its starting vertex.
- The graph may be disconnected; a cycle anywhere counts.
- A self-loop
u → uis a cycle of length one.
The task is to detect cycle in directed graph using BFS, so the answer must come from a queue rather than recursion. With up to 10⁵ vertices and edges, the check has to be linear in V + E.
- 1 <= V <= 10⁵
- 0 <= E <= 10⁵
- Fewer than V vertices emitted proves a cycle
Intuition
Turn the question around: instead of hunting for a cycle, try to list the vertices so every edge points forward. That ordering is a topological sort, and it exists exactly when the graph has no cycle.
A vertex with in-degree 0 has nothing that must come before it, so it can go first; removing it may free its successors in turn. Peeling vertices this way from a queue is Kahn's algorithm.
On a cycle a → b → c → a, every vertex keeps an incoming edge from another cycle vertex, so none can ever go first. The peeling stalls, and the number of removed vertices ends below V. That shortfall is the whole cycle test.
The detect cycle in directed graph BFS method fits when the graph is directed and you need a yes/no on cycles without recursion, or when you also want an ordering: course prerequisites (Course Schedule, LeetCode 207 and 210), build systems, spreadsheet formula dependencies, package installs. If the question is undirected, this method does not apply: every undirected edge counts towards both ends, so in-degrees never drop the same way.
Approach
Before reading on: in the graph 0 → 1 → 2 → 3 → 1 with an extra edge 3 → 4, vertex 4 is not on any cycle. Will Kahn's algorithm ever remove it? What does that tell you about using the leftover vertices as "the cycle"?
Build the adjacency list and in-degrees together
For each edge [u, v], append v to adj[u] and add 1 to indeg[v]. One pass over the edges gives both, and indeg[v] is now the number of vertices that must be removed before v is free.
Seed the queue with every in-degree-0 vertex
Scan all V vertices and queue each one whose in-degree is 0, not just vertex 0. In a disconnected graph each component has its own sources, and a source left out would leave its whole downstream unremoved.
Peel: pop, count, release successors
Pop a vertex u and add 1 to removed. For each v in adj[u], subtract 1 from indeg[v], since the edge u → v is gone. Push v only when indeg[v] reaches 0, so each vertex enters the queue exactly once.
Compare the count with V
When the queue empties, return removed < V. Equal means every vertex was peeled and the removal order is a valid topological order; fewer means some vertices waited forever on each other.
Why a short count means a cycle
Every DAG has a vertex with in-degree 0, and removing it leaves a smaller DAG, so without a cycle the peel never stalls. On a cycle, the first vertex to go would need in-degree 0 while its predecessor on the cycle is still present, so no cycle vertex is ever removed.
Detect Cycle in Directed Graph (BFS) solution in Python | C++ | Java
Common pitfalls
Reusing the undirected BFS parent check
if visited[v] and v != parent[u]:
return Trueindeg[v] -= 1
if indeg[v] == 0:
queue.append(v)In a directed graph, reaching an already-visited vertex is normal: 0 → 1, 0 → 2, 1 → 3, 2 → 3 reaches 3 twice with no cycle. The parent trick only works when every edge goes both ways.
Seeding the queue with vertex 0 only
queue = deque([0])
queue = deque(u for u in range(V) if indeg[u] == 0)
Vertex 0 may itself have incoming edges, and other components have their own sources. Missing a source leaves its whole downstream unremoved, which is then misreported as a cycle.
Pushing a vertex every time its in-degree drops
indeg[v] -= 1 queue.append(v)
indeg[v] -= 1
if indeg[v] == 0:
queue.append(v)A vertex with two predecessors would be pushed twice and counted twice, so removed can reach V even when a cycle exists. Push only at the moment the count hits 0.
Returning the leftover vertices as "the cycle"
return [u for u in range(V) if indeg[u] > 0]
return removed < V # yes / no only
Leftovers include every vertex downstream of a cycle, not just the cycle itself. To print the actual cycle, follow remaining edges from a leftover vertex until a vertex repeats.
Edge cases
The loop adds 1 to indeg[u] and only u itself could remove it, so u is never peeled and the answer is true.
Complexity
adj and indeg, and once more when its source is removed. Each vertex enters the queue at most once. The adjacency list takes O(V + E); the queue and indeg take O(V).Cycle detection: which method for which graph
The BFS idea changes completely between directed and undirected graphs, which is where most wrong answers come from.
| Method | Graph | Cycle when | Also gives |
|---|---|---|---|
| Kahn's algorithm (BFS, in-degrees) | Directed | fewer than V vertices removed | a topological order |
| DFS with 3 states | Directed | an edge reaches a vertex still on the recursion path | a back edge to print the cycle |
| BFS with parent tracking | Undirected | a visited neighbour that is not the parent | nothing extra |
| Union-Find | Undirected | an edge joins two vertices already in one set | connected components |
Detect Cycle in Directed Graph (BFS) FAQ
Is Kahn's algorithm BFS?
Yes in mechanics: it processes vertices from a FIFO queue, level by level of dependency. It does not compute shortest distances like textbook BFS, though, and a stack instead of a queue gives an equally valid topological sort and the same cycle answer.
Should I use BFS or DFS for cycle detection in directed graph problems?
Both are O(V + E). Prefer BFS (Kahn's algorithm) when you also need the order, as in Course Schedule II, or when the graph can be deep enough to overflow the recursion stack. Prefer DFS when you need to report the cycle itself, because the recursion path holds it.