You can create a depth-first search function with a stack or with recursion (which employs a call stack). The recursive implementation is far more common, so that’s how you’ll do it here.
Ok, roll up your sleeves and get ready to build the recursive case for your function…
This part of the function will go something like:
loop through each neighbor of the current vertex in the graph: if neighbor has not been visited: recursively call dfs on neighbor if a path exists: return the path
Instructions
Below your base case, open a Python for
loop to check each neighbor
of the current_vertex
in our graph.
We don’t want to revisit vertices that have already been checked, so add an if
clause here that makes sure neighbor
hasn’t already been added to visited
.
Inside the if
clause, set path
equal to a call of dfs()
with the following arguments:
graph
(the graph hasn’t changed)neighbor
(this is the newcurrent_vertex
within the function call)target_value
(the value we are still looking for)visited
(now a list of at least one vertex value)
We don’t want DFS to return None
just because the first route it checked didn’t exist.
Check if path
exists. If so, return path
.
Test out your DFS function!
Outside of the function, call dfs()
on the graph provided with a start vertex of "crocodiles"
and a target value of "bees"
.
Don’t forget to print out the result to see the path in the terminal!