Detecting a cycle in a directed graph

Question

I read a discussion here, at SO about finding a cycle in a directed graph. Now, the OP claims that we need to validate two things:

1. There's a back edge from u to v
2. v is in the recursion-stack

Why do we need the second test? Could you give an example to demonstrate it's necessity?

Answer 1

Well, you probably got confused between the definition of a back-edge in a directed graph and a back-edge in an undirected graph. Yes, they are different.

While in undirected graph back edges are edges from the current vertex to an-already-visited vertex. (as OP from your link mentioned).
In directed graph the definition for back edge is different. A back edge in a directed graph is an edge from current vertex to a GREY vertex (the DFS for this vertex has started but not yet finished), meaning it is still in the recursion stack.

So if you take the definition of a back edge as it is in a directed graph then yes, it is enough for detecting a cycle.
But if you take the definition of a back edge as it is in an undirected graph then you will need also to make sure that v is in the recursion stack in order to detect a cycle.

See this and this for more information and examples.

Example:
Consider the DFS visit order to be A -> B -> C.
In this example, the edge <A,C> is a back edge in the undericted graph (as C was already visited).
But it is not a back edge in this directed graph - C was already visited but is not in the recursion stack, meaning it is not a cycle.

Answer 2

Only the fact that we already visited v is not sufficient. It allows us to go from u to v, but not from v to u.

Simple graphical counterexample:

Numbers are traversal order. We have a back edge from 4 to 3, but we don't have any cycles.