evolution, more robustly. To see a data structure that departs even further from the
built-in gang, though, we need to move on to the next section.
Graph Searching
Many problems that crop up in both real life and real programming can be fairly rep-
resented as a graph—a set of states with transitions (“arcs”) that lead from one state
to another. For example, planning a route for a trip is really a graph search problem in
disguise: the states are places you’d like to visit, and the arcs are the transportation
links between them. A program that searches for a trip’s optimal route is a graph
searcher. For that matter, so are many programs that walk hyperlinks on the Web.
This section presents simple Python programs that search through a directed, cyclic
graph to find the paths between a start state and a goal. Graphs can be more general
than trees because links may point at arbitrary nodes—even ones already searched
(hence the word cyclic). Moreover, there isn’t any direct built-in support for this type
of goal; although graph searchers may ultimately use built-in types, their search routines
are custom enough to warrant proprietary implementations.
The graph used to test searchers in this section is sketched in Figure 18-1. Arrows at
the end of arcs indicate valid paths (e.g., A leads to B, E, and G). The search algorithms
will traverse this graph in a depth-first fashion, and they will trap cycles in order to
avoid looping. If you pretend that this is a map, where nodes represent cities and arcs
represent roads, this example will probably seem a bit more meaningful.
Figure 18-1. A directed graph
Implementing Graph Search
The first thing we need to do is choose a way to represent this graph in a Python script.
One approach is to use built-in datatypes and searcher functions. The file in Exam-
ple 18-16 builds the test graph as a simple dictionary: each state is a dictionary key,
1390 | Chapter 18: Data Structures