Many problems that crop up in both real life and real programming can be fairly represented 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
The first ...