Cycle Detection (DFS)
Detects a directed cycle by three-coloring nodes during DFS: gray means "on the current path". An edge into a gray node is a back edge and proves a cycle exists.
- Category
- Graphs
- Time complexity
- O(V + E)
- Space complexity
- O(V)
Pseudocode
color node gray on entry if a neighbor is gray → cycle color black when fully explored no back edge ⇒ acyclic
Reference implementation
def dfs(u):
color[u] = GRAY
for v in adj[u]:
if color[v] == GRAY: return True # cycle
if color[v] == WHITE and dfs(v): return True
color[u] = BLACK