Skip to main content
Computer Science

Return to Question

Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
improve title.
Link
Discrete lizard ♦
Discrete lizard ♦
  • 8.3k
  • 3
  • 24
  • 53

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

Improve formatting, it's/its
Source Link
dkaeae
dkaeae
  • 5k
  • 1
  • 16
  • 31

Directed graph that returns before all it'sits child nodes are visited?

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.

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 itsit's not complete?

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

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

Directed graph that returns before all it's child nodes are visited?

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 its not complete?

I just cant see a scenario where this would happen.

It would never return, since DFS is (essentially) recursive and it cant return without hitting all base cases.

Directed graph that returns before all its child nodes are visited?

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.

Source Link
Peter
Peter
  • 21
  • 1

Directed graph that returns before all it's child nodes are visited?

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 its not complete?

I just cant see a scenario where this would happen.

It would never return, since DFS is (essentially) recursive and it cant return without hitting all base cases.