2
$\begingroup$

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.

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

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

$\endgroup$

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.