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. That skeleton key is traversal: discovering, and later ...