Graph Theory

[If you're already comfortable with graph theory, skip ahead to Reachability.]

For a rather math-intensive introduction to graph theory, see Wikipedia. Here's a very short version of the definition they use there:

A graph refers to a collection of nodes and a collection of edges that connect pairs of nodes.

Graph theory can be used to describe a lot of things, but I'll start off with one of the most straightforward examples: maps. You can think of graph theory as a way of encoding information about two aspects of a map: places to go, and ways to get there.

Let's start at the very beginning, shall we?

[By the way: as important human inventions go, I happen to think graph theory is right up there alongside bacon and indoor plumbing. It takes some time to really sink in, though, so if you find your eyes glazing over in this section, don't worry about it. As long as the page about reachability makes sense to you, you can come back and reread these pages later.]