Grokking Algorithms

Chapter 6
 
 
I
 
 
Breadth-first search
If you enqueue two items to the list, the first item you added will be 
dequeued before the second item. You can use this for your search list! 
People who are added to the list first will be dequeued and searched 
first.
The queue is called a 
FIFO
data structure: First In, First Out. In 
contrast, a stack is a 
LIFO
data structure: Last In, First Out.
Now that you know how a queue works, let’s implement breadth-first 
search!
EXERCISES
Run the breadth-first search algorithm on each of these graphs to find 
the solution.
6.1
Find the length of the shortest path
from start to finish.
6.2
Find the length of the shortest path
from “cab” to “bat”.

---

105
Implementing the graph
Implementing the graph
First, you need to implement the graph in code. A graph 
consists of several nodes.
And each node is connected to neighboring nodes. 
How do you express a relationship like “you -> bob”? 
Luckily, you know a data structure that lets you express 
relationships: 
a hash table
!
Remember, a hash table allows you to map a key to a 
value. In this case, you want to map a node to all of its 
neighbors.
Here’s how you’d write it in Python:
graph = {}
graph[“you”] = [“alice”, “bob”, “claire”]
Notice that “you” is mapped to an array. So 
graph[“you”]
will give you 
an array of all the neighbors of “you”.
A graph is just a bunch of nodes and edges, so this is all you need to 
have a graph in Python. What about a bigger graph, like this one?

---

106