Direction changes everything
In a directed graph, edges point one way, so detecting cycles needs more care than the undirected case. The key tool is tracking which vertices are currently on the recursion stack of a depth first search.
Three colours
A common formulation paints each vertex one of three colours:
- White means not yet visited.
- Grey means visited and still on the active recursion stack.
- Black means fully explored and removed from the stack.
While exploring, if you follow an edge to a grey vertex, that vertex is an ancestor in the current path, so you have found a back edge and therefore a directed cycle. Reaching a black vertex is fine; it was finished on a different branch.
Why grey is the signal
A grey vertex means the search is still in the middle of exploring it. An edge pointing back to it proves the path can loop around to an ancestor, which is precisely a cycle.
A directed graph with no cycles is a directed acyclic graph, the prerequisite for topological sorting and for scheduling tasks with dependencies.
Key idea
In a directed graph a cycle appears when a DFS follows an edge into a grey vertex still on the recursion stack, signalling a back edge to an ancestor.