Learn

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

1.

Inside the for loop, add an if clause that checks to be sure that neighbor is not already in our set of visited vertices.

2.

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.

3.

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 with neighbor appended to it
4.

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?

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?