You’re back in a car, but this time, your friend “B” is navigating. Unlike D, B is a bit hesitant about whether you’ve gone the right way and keeps checking in to see if you are on the best path. At each intersection, B tries out each possible route one by one, but only for a block in each direction to see if you’ve found your destination.

Like B, breadth-first search, known as *BFS*, checks the values of all neighboring vertices before moving into another level of depth.

This is an incredibly inefficient way to find just *any* path between two points, but it’s an excellent way to identify the *shortest path* between two vertices. Because of this, BFS is helpful for figuring out directions from one place to another.

Unlike DFS, BFS graph search implementations use a queue data structure to keep track of the current vertex and vertices that still have unvisited neighbors. In BFS graph search a vertex is dequeued when all neighboring vertices have been visited.

### Instructions

Watch the video to see a breadth-first search in action, then take a look at the city map below. How could you use BFS to find the shortest walking route between Casa Batlló and the Sagrada Familia?