Grokking Algorithms

Breadth-first search
We looked at a search algorithm in chapter 1: binary search. Breadth-
first search is a different kind of search algorithm: one that runs on 
graphs. It can help answer two types of questions:
• Question type 1: Is there a path from node A to node B?
• Question type 2: What is the shortest path from node A to node B?
Graph of people who owe
other people poker money

---

100
Chapter 6
 
 
I
 
 
Breadth-first search
You already saw breadth-first search once, when you calculated the 
shortest route from Twin Peaks to the Golden Gate Bridge. That was 
a question of type 2: “What is the shortest path?” Now let’s look at the 
algorithm in more detail. You’ll ask a question of type 1: “Is there a 
path?”
Suppose you’re the proud owner of a mango farm. You’re looking for a 
mango seller who can sell your mangoes. Are you connected to a mango 
seller on Facebook? Well, you can search through your friends.
This search is pretty straightforward.
First, make a list of friends to search.

---

101
Breadth-first search
Now, go to each person in the list and check whether that person sells 
mangoes.
Suppose none of your friends are mango sellers. Now you have to 
search through your friends’ friends.
Each time you search for someone from the list, add all of their friends 
to the list.

---

102
Chapter 6
 
 
I
 
 
Breadth-first search
This way, you not only search your friends, but you search their friends, 
too. Remember, the goal is to find one mango seller in your network. 
So if Alice isn’t a mango seller, you add her friends to the list, too. That 
means you’ll eventually search her friends—and then their friends, and 
so on. With this algorithm, you’ll search your entire network until you 
come across a mango seller. This algorithm is breadth-first search.