Detect Cycle in a Graph —
A back edge to a node still on the stack.
A cycle in a directed graph means you can follow edges and end up back where you started. DFS finds this with three colors instead of a simple visited flag — white (untouched), grey (in progress, still on the current path), black (fully done). Watch a node go white → grey → black on LearnBug and see the exact edge that reveals a back-to-grey cycle.
What is Cycle Detection?
Run DFS and color each node: white before it's visited, grey while it's still on the current recursion path, black once its entire subtree is fully explored. If DFS ever follows an edge into a node that is currently grey, that node is an ancestor on the current path — a back edge — which means a cycle exists.
Why visualization helps
A plain visited/unvisited flag isn't enough — it can't tell "already fully explored" apart from "still being explored right now," which is exactly the distinction that matters for a directed cycle. LearnBug shows each node's color changing live, so the moment a grey node gets revisited — the actual cycle-revealing event — is visibly obvious.
The parent edge trap
Directed graph — 3-color DFS ✓
A back edge to any grey (currently-on-path) node is a cycle. Edges only go one way, so this is the reliable check.
Undirected graph — track the parent
Every edge is bidirectional, so a visited neighbor isn't automatically a cycle — you must exclude the edge you just arrived from.
Real-world use
Deadlock detection (resource allocation graphs) and prerequisite validation (course/dependency graphs) both boil down to this check.
Cycle check on A→B, B→C, C→A
Start dfs(A): color A grey, recurse into its neighbor B
A is now "in progress" — on the current DFS path. B is still white (untouched), so the recursion continues into it.
dfs(B): color B grey, recurse into its neighbor C
Same pattern — B joins the current path, and its neighbor C is still white, so DFS dives in.
dfs(C): color C grey, check its neighbor A — A is grey!
C's only neighbor is A, and A is currently grey — meaning A is still an ancestor on this exact recursion path. This edge C→A is a back edge, which means a cycle exists: A → B → C → A.
Return: True — cycle found ✓ via the back edge C→A
3-color DFS cycle detection
graph = {
"A": ["B"],
"B": ["C"],
"C": ["A"],
}
WHITE, GREY, BLACK = 0, 1, 2
color = {node: WHITE for node in graph}
def has_cycle(node):
color[node] = GREY # mark "on the current path"
for neighbor in graph[node]:
if color[neighbor] == GREY:
return True # back edge to an ancestor — cycle!
if color[neighbor] == WHITE and has_cycle(neighbor):
return True
color[node] = BLACK # fully explored, safe forever
return FalseComplexity Notes
Frequently asked questions
Why do I need three colors instead of a simple visited set?
A plain visited set can't tell "this node is an ancestor on my current DFS path" apart from "this node was fully explored on a completely different branch earlier." Only the first case is a cycle. Grey means the former; black means the latter — and only revisiting a grey node indicates a cycle.
How does cycle detection differ for undirected graphs?
In an undirected graph, every edge is stored both ways — if A-B is an edge, B sees A as a neighbor too. So visiting B from A and then seeing A again from B is expected, not a cycle. You must pass along the parent node and skip the edge straight back to it; only a visited node that isn't the immediate parent indicates a real cycle.
What real problems use cycle detection?
Course scheduling (can't have A requires B requires A), build systems and package managers (circular dependencies), and operating systems deadlock detection (resource allocation graphs) are all instances of the same directed-cycle check.
Can I detect a cycle with BFS instead of DFS?
For directed graphs, yes — Kahn's algorithm (topological sort via BFS) naturally detects a cycle: if the algorithm finishes without processing every node, whatever's left over is part of a cycle. See the Topological Sort lesson for exactly how that works.
Watch a node turn grey, then reveal the back edge
Paste your cycle detection into LearnBug and see the color states change live.