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
.
|