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.
Dostları ilə paylaş: 
