Chapter 5. Traversal: The Skeleton Key of Algorithmics


You are in a narrow hallway. This continues for several metres and ends in a doorway. Halfway along the passage you can see an archway where some steps lead downwards. Will you go forwards to the door (turn to 5), or creep down the steps (turn to 344)?

 --Steve Jackson, Citadel of Chaos

Graphs are a powerful mental (and mathematical) model of structure in general; if you can formulate a problem as one dealing with graphs, even if it doesn't look like a graph problem, you are probably one step closer to solving it. It just so happens that there is a highly useful mental model for graph algorithms as well—a skeleton key, if you will.[50] That skeleton key is traversal: discovering, and later ...

Get Python Algorithms: Mastering Basic Algorithms in the Python Language now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.