# Directed graph where DFS returns on a node before all its child nodes are visited?

Give an example of a directed graph in which a depth-ﬁrst search backs up from a vertex $$v$$ before all the vertices that can be reached from $$v$$ via one or more edges are discovered.

My professor recently asked this question as a warm up to lecture, but never answered it. I still have not figure how that is possible. Why would it return if it's not complete?

I just can't see a scenario where this would happen.

It would never return, since DFS is (essentially) recursive and it can't return without having hit all base cases.

• Hint: what does DFS do when it detects a cycle? – Discrete lizard Apr 17 '19 at 9:09

I am not sure what does he mean by 'back up from a vertex $$v$$'. If he just means an encounter of parent node then the case is shown in the pic. $$s$$ is the starting node in the algorithm. Flow might return to $$s$$ before going to leaves of $$v$$ making the edge $$(v,s)$$ back edge.