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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Hint: what does DFS do when it detects a cycle? $\endgroup$
    – Discrete lizard ♦
    Commented Apr 17, 2019 at 9:09

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
-1
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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