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