Grokking Algorithms

Finding the shortest path
As a recap, these are the two questions that breadth-first search can 
answer for you:
• Question type 1: Is there a path from node A to node B? (Is there a 
mango seller in your network?)
• Question type 2: What is the shortest path from node A to node B? 
(Who is the closest mango seller?)
You saw how to answer question 1; now let’s try to answer question 
2. Can you find the closest mango seller? For example, your friends 
are first-degree connections, and their friends are second-degree 
connections.

---

103
Breadth-first search
You’d prefer a first-degree connection to a second-degree connection, 
and a second-degree connection to a third-degree connection, and so 
on. So you shouldn’t search any second-degree connections before you 
make sure you don’t have a first-degree connection who is a mango 
seller. Well, breadth-first search already does this! The way breadth-first 
search works, the search radiates out from the starting point. So you’ll 
check first-degree connections before second-degree connections. Pop 
quiz: who will be checked first, Claire or Anuj? Answer: Claire is a first-
degree connection, and Anuj is a second-degree connection. So Claire 
will be checked before Anuj.
Another way to see this is, first-degree connections 
are added to the search list before second-degree 
connections.
You just go down the list and check people to see 
whether each one is a mango seller. The first-degree 
connections will be searched before the second-
degree connections, so you’ll find the mango seller 
closest to you. Breadth-first search not only finds a 
path from A to B, it also finds the shortest path.
Notice that this only works if you search people in the same order in 
which they’re added. That is, if Claire was added to the list before Anuj, 
Claire needs to be searched before Anuj. What happens if you search 
Anuj before Claire, and they’re both mango sellers? Well, Anuj is a 
second-degree contact, and Claire is a first-degree contact. You end up 
with a mango seller who isn’t the closest to you in your network. So 
you need to search people in the order that they’re added. There’s a data 
structure for this: it’s called 
a queue
.
Queues
A queue works exactly like it does in 
real life. Suppose you and your friend 
are queueing up at the bus stop. If you’re 
before him in the queue, you get on the 
bus first. A queue works the same way. 
Queues are similar to stacks. You can’t 
access random elements in the queue. 
Instead, there are two only operations, 
enqueue
and 
dequeue
.

---

104