Breadth-First Search

Think About It...

Think back to our earlier lessons on autonomous vehicles. As we begin this lesson, ask yourself a few questions:

How does a self-driving vehicle know which route to follow?
How do GPS navigation systems create directions for drivers?

Pins mark locations on a map

Humans Finding a Path

In this portion of our lesson we will learn about and complete a search tree using breadth-first search. Imagine you and your friends are visiting an amusement park and you want to find the shortest route to your favorite ride. The park is big, with lots of paths and attractions. You don’t want to miss any possible shortcuts, so you decide to use a systematic approach.

Here’s how breadth-first search can help you:

Start at the entrance: Utilizing a park map (representation of your environment), the entrance is your starting point, the root node of your search tree.
Explore nearby paths: Look at all the paths directly connected to the entrance. These are the nodes one step away. Maybe there’s a path to the VR ride, the food court, and the bumper cars.
Move to the next level: After checking all paths one step away, look at the paths two steps away.
Keep going: Continue this process, exploring nodes level by level, until you find the path to your chosen ride.

By using breadth-first search, you check all attractions and paths closest to the entrance first. Then you check paths further away, ensuring that you explore every possible route methodically.

Now, let’s apply that to our questions: how does a self-driving vehicle know which route to follow OR how do GPS navigation systems create directions for drivers? For this example we will determine the best route to destination city.

GPS Routing - Activity

Follow along in the Route Finding Guided Activity for an in-depth understanding of route finding. You can also download the activity.

[CC BY-NC-SA 4.0] UNLESS OTHERWISE NOTED | IMAGES: LICENSED AND USED ACCORDING TO TERMS OF SUBSCRIPTION - INTENDED ONLY FOR USE WITHIN LESSON.
Triff/Shutterstock.com. Image used under license from Shutterstock.com and may not be repurposed.