Grokking Algorithms

Chapter 6
 
 
I
 
 
Breadth-first search
Next, you check yourself. You’re not a mango seller, so you add all of 
your neighbors to the search queue.
And so on. This will be an infinite loop, because the search queue will 
keep going from you to Peggy.
Before checking a person, it’s important to make sure 
they haven’t been checked already. To do that, you’ll 
keep a list of people you’ve already checked.
Here’s the final code for breadth-first search, taking that into account:
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = [] 
while search_queue:
person = search_queue.popleft()
if not person in searched: 
if person_is_seller(person):
print person + “ is a mango seller!”
return True
else:
search_queue += graph[person]
searched.append(person)
return False
search(“you”)
This array is how you keep track of 
which people you’ve searched before.
Only search this person if you
haven’t already searched them.
Marks this person as searched

---

111
Implementing the algorithm
Try running this code yourself. Maybe try changing the 
person_is_
seller
function to something more meaningful, and see if it prints 
what you expect.
Running time
If you search your entire network for a mango seller, that means you’ll 
follow each edge (remember, an edge is the arrow or connection from 
one person to another). So the running time is at least O(number of 
edges).
You also keep a queue of every person to search. Adding one person to 
the queue takes constant time: O(1). Doing this for every person will 
take O(number of people) total. Breadth-first search takes O(number of 
people + number of edges), and it’s more commonly written as O(V+E) 
(V for number of vertices, E for number of edges).
EXERCISE
Here’s a small graph of my morning routine.
It tells you that I can’t eat breakfast until I’ve brushed my teeth. So “eat 
breakfast” 
depends on
“brush teeth”.
On the other hand, showering doesn’t depend on brushing my teeth, 
because I can shower before I brush my teeth. From this graph, you can 
make a list of the order in which I need to do my morning routine:
1. Wake up.
2. Shower.
3. Brush teeth.
4. Eat breakfast.

---

112