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
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
if clause, set
path equal to a call of
dfs() with the following arguments:
graph(the graph hasn’t changed)
neighbor(this is the new
current_vertexwithin 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.
path exists. If so, return
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
Don’t forget to print out the result to see the path in the terminal!