108
Chapter 6
I
Breadth-first search
Let’s see the rest:
while search_queue:
person = search_queue.popleft()
if person_is_seller(person):
print person + “ is a mango seller!”
return True
else:
search_queue += graph[person]
return False
One final thing: you still need a
person_is_seller
function to tell you
when someone is a mango seller. Here’s one:
def person_is_seller(name):
return name[-1] == ‘m’
This function checks whether the person’s
name ends with the letter
m
.
If it does, they’re a mango seller. Kind of a silly way to do it, but it’ll do
for this example. Now let’s see the breadth-first search in action.
While the queue isn’t empty …
… grabs the first person off the queue
Checks whether the person is a mango seller
Yes, they’re a mango seller.
No, they aren’t. Add all of this
person’s friends to the search queue.
If you reached here, no one in
the queue was a mango seller.
109
Implementing the algorithm
And so on. The algorithm will keep going until either
• A mango seller is found, or
•
The queue becomes empty, in which case there is no mango seller.
Alice and Bob share a friend: Peggy. So Peggy will be added to the
queue twice: once when you add Alice’s friends, and again when you
add Bob’s friends. You’ll end up with two Peggys in the search queue.
But you only need to check Peggy once to see whether she’s
a mango
seller. If you check her twice, you’re doing unnecessary, extra work. So
once
you search a person, you should mark that person as searched and
not search them again.
If you don’t do this, you could also end up in an infinite loop. Suppose
the mango seller graph looked like this.
To start, the search queue contains all of your neighbors.
Now you check Peggy. She isn’t
a mango seller, so you add all of her
neighbors to the search queue.
