Many problems can be represented as a graph, which is 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.

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

The graph used to test searchers in this section is sketched in
Figure 20-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 20-1. A directed graph

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 Example 20-15 builds the test graph as a simple dictionary: each state is a dictionary key, with a list of keys of nodes it leads to (i.e., its arcs). This file also defines ...

Start Free Trial

No credit card required