We don’t want to do anything with neighbors that we’ve already visited, so we’ll skip those. Having narrowed our search down to unvisited neighboring vertices, there are two possibilities:
- The vertex has the value we’ve been looking for.
- The vertex doesn’t have the value we’re looking for and so we want to add it to the queue.
Our code will follow this logic:
if neighbor has not been visited: if neighbor is equal to target_value: return path including neighbor else: add neighbor and its path to the queue
Instructions
Inside the for
loop, add an if
clause that checks to be sure that neighbor
is not already in our set of visited vertices.
Inside the if
clause, create another if
condition for the case that neighbor
is the target_value
.
If it is, return path
with neighbor
appended to it.
Create an else
condition to handle the case that we need to keep searching because neighbor
is not the target_value
.
Inside the else
, append a list to bfs_queue
that contains two elements:
neighbor
(the vertex)- the
path
list withneighbor
appended to it
Call bfs()
on the graph in the code editor with a start vertex of “crocodiles” and a target value of “bees” and print the result!
Is the shortest path what you expected?