Grokking Algorithms

Chapter 6
 
 
I
 
 
Breadth-first search
Aha! Now the Golden Gate Bridge shows up. So it takes three steps to 
get from Twin Peaks to the bridge using this route.
There are other routes that will get you to the bridge too, but they’re 
longer (four steps). The algorithm found that the shortest route to the 
bridge is three steps long. This type of problem is called a 
shortest-path 
problem
. You’re always trying to find the shortest something. It could 
be the shortest route to your friend’s house. It could be the smallest 
number of moves to checkmate in a game of chess. The algorithm to 
solve a shortest-path problem is called
 breadth-first search
.
To figure out how to get from Twin Peaks to the Golden Gate Bridge, 
there are two steps:
1. Model the problem as a graph.
2. Solve the problem using breadth-first search.
Next I’ll cover what graphs are. Then I’ll go into breadth-first search in 
more detail.
What is a graph?
A graph models a set of connections. For 
example, suppose you and your friends are 
playing poker, and you want to model who owes 
whom money. Here’s how you could say, “Alex 
owes Rama money.”

---

99
Breadth-first search
The full graph could look something like this.
Alex owes Rama money, Tom owes Adit money, and so on. Each graph 
is made up of 
nodes
and 
edges
.
That’s all there is to it! Graphs are made up of nodes and edges. A node 
can be directly connected to many other nodes. Those nodes are called 
its 
neighbors
. In this graph, Rama is Alex’s neighbor. Adit isn’t Alex’s 
neighbor, because they aren’t directly connected. But Adit is Rama’s and 
Tom’s neighbor.
Graphs are a way to model how different things are connected to one 
another. Now let’s see breadth-first search in action.