Give an example of a directed graph in which a depth-first 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.

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

Consider the following graph. If DFS will first go to the second node, it will back up even though the third node is reachable from the second.

The example graph

New contributor
IS3NY is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

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.

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.