Graph AlgosGraph Algorithms

Cycle Detection (directed, 3-color DFS)

Decide whether a graph has a cycle: three-colour DFS for directed graphs; DFS with parent tracking or union-find for undirected graphs.

Learn Cycle Detection →
ABCDEFGH
Gray path
empty
1/6Three-color DFS: white = unseen, gray = on the current path, black = finished. A directed cycle exists exactly when DFS meets an edge into a gray node.
Current nodeGray: on the current DFS pathBlack: fully exploredTree edgeBack edge (closes a cycle)
PseudocodeLearn Cycle Detection →
1color[v] = WHITE for all v
2def dfs(u):
3  color[u] = GRAY   # on the current path
4  for v in neighbors(u):
5    if color[v] == GRAY: return cycle (back edge u→v)
6    if color[v] == WHITE and dfs(v): return true
7  color[u] = BLACK; return false
8for u in nodes: if color[u] == WHITE and dfs(u): report cycle
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed