Learn

Unlike DFS, BFS is primarily concerned with the shortest path that exists between two points, so that’s what we’ll be thinking about as we build out our breadth-first search function.

Using a queue will help us keep track of the current vertex and its corresponding path. Unlike with DFS, with BFS we may have to expand on paths in several directions to find the path we’re looking for. Because of this, our path is not the same as our visited vertices.

For visited we don’t care about the order of visitation; we only care about whether a vertex is visited or not, so we’ll use a Python set. Our breadth-first search logic should begin something like this:

def bfs(graph, start_vertex, target_value):

  set path to a list containing the start_vertex

  create a queue to hold vertices and their corresponding paths

  define an empty visited set

Instructions

Define a function bfs() with the following parameters:

graph (again, the graph we’re passing in)
start_vertex (our starting point within the graph)
target_value (the value we seek)

In the body of the function, define a variable path and set it equal to a list that contains start_vertex. We’ll collect more values in here as we go along.

For now, return path and outside the function, print a call of bfs(None, "lava!", None). You should see ['lava!'] in the terminal.

Remove the return statement and the printed bfs() call.

Next, back inside the function, define a variable vertex_and_path as a list that contains start_vertex and our newly minted path variable.

Where’s that queue we’re supposed to use? We’re creating it now.

Create a variable bfs_queue and set it equal to a list that contains vertex_and_path. We’ll use this to keep track of each vertex-path combination.

On the next line within bfs(), define visited as an empty set.

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?