Graph DFS detecting cycles - (supposed) counterexample

Question

So a DFS should detect cycles in a directed graph. If it reaches a node that has already been visited previously, i.e. it finds a back-edge, then we have a cycle.

I found a graph in which I can't see how this is the case. I know there must be a flaw in how I'm thinking, so if anyone can help me out it would be great.

So here's the graph with the adjacency list (drawing it didn't exactly work...):

A | B
B | C, D
C | F
D | E
E |
F | E

Assuming the DFS starts from A, and when it gets to B, pushes C before D to the stack, then it will reach node E first, and then mark it visited. Then it will pop node C, go to F, then find E in F's adjacency list and E is already visited, thus giving a cycle. But there's really no cycle in the graph.

Where's the flaw in my reasoning?

Answer 1

The flaw here is that revisiting a node during a DFS doesn't necessarily give a back edge. It can also give a cross edge or forward edge, which is the case here. A back edge only occurs when the node you revisit has started being explored but has not had all of its children processed. In this case, since E already has had all of its children processed, the edge on which it's encountered a second time isn't a back edge, so no cycle should be reported.

Hope this helps!