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
for loop, add an
if clause that checks to be sure that
neighbor is not already in our set of visited vertices.
if clause, create another
if condition for the case that
neighbor is the
If it is, return
neighbor appended to it.
else condition to handle the case that we need to keep searching because
neighbor is not the
else, append a list to
bfs_queue that contains two elements:
neighborappended to it
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?