Skip to Main Content
Programming Python, 3rd Edition
book

Programming Python, 3rd Edition

by Mark Lutz
August 2006
Intermediate to advanced content levelIntermediate to advanced
1600 pages
51h 46m
English
O'Reilly Media, Inc.
Content preview from Programming Python, 3rd Edition

Graph Searching

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.

A directed graph

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

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Learning Python, 3rd Edition

Learning Python, 3rd Edition

Mark Lutz

Publisher Resources

ISBN: 0596009259Supplemental ContentErrata Page