Directed Graph — Cycle Detection

Interactive visualization of DFS cycle detection with adjacency lists and three-color marking

Directed Graph — Cycle Detection

DFS with WHITE / GRAY / BLACK coloring for course prerequisites

Show Adj List

Choose a preset and run DFS cycle detection

Adjacency List

CS101:[CS201]

CS201:[CS301]

CS301:[CS401]

CS401:[CS101]

# Build adjacency list

adj = {4 empty lists}

adj[0].append(1)

adj[1].append(2)

adj[2].append(3)

adj[3].append(0)

WHITE (unvisited)GRAY (in progress)BLACK (finished)Cycle

How Cycle Detection Works

1. WHITE

Node hasn't been visited yet. We start DFS from it.

2. GRAY

Node is being processed (on the call stack). If we reach a GRAY node, we found a back edge = cycle!

3. BLACK

Node and all its descendants are fully explored. Safe to skip.

Why does finding a GRAY neighbor mean a cycle?

GRAY nodes are on the current DFS path. If node A is GRAY and we reach A again from one of its descendants, that means there's a path from A back to A — a cycle. This is called a back edge in graph terminology.

Course Schedule meaning: If course A requires B, and B (directly or indirectly) requires A, you can never complete either — that's a cycle in the prerequisite graph.

Time Complexity

Operation	Time	Why
Build adj list	`O(E)`	One pass through all edges
DFS cycle detection	`O(V + E)`	Visit each node once, check each edge once
Space	`O(V + E)`	Adjacency list + color array + recursion stack