Cycles in directed graphs
A cycle in a directed graph is a path that follows edge directions and returns to where it started. Detecting cycles matters for scheduling, dependency resolution, and deadlock analysis. A directed graph with no cycle is a directed acyclic graph or DAG.
Three colors
The standard method runs a depth first search and tags each vertex with one of three states, often called colors.
- White means not yet visited.
- Gray means currently on the recursion stack, still being explored.
- Black means fully explored, recursion finished.
During the search, if you follow an edge to a gray vertex, you have found a back edge, which proves a cycle exists. An edge to a black vertex is fine because that subtree is already settled.
Why the gray check works
A gray vertex is an ancestor of the current vertex in the DFS tree. Reaching an ancestor again means there is a path forward that loops back, the definition of a cycle. Resetting the color to black on the way out keeps later branches from raising false alarms.
Key idea
Run DFS with three colors and report a cycle the moment you find an edge into a gray vertex still on the recursion stack.