The next step in my preparation for the CS GRE is graph theory. The cool thing about graph theory is it is the basis for representing anything to do with relationships, especially spacial relationships.

I have GPS system in my car that routinely gets me to locations via routes I didn’t know. It is certainly not always the fastest route, but it works. If only I had that as an Platoon Leader. Actually, I did have a GPS, but it didn’t do route finding. Just told you where you were. I wonder how many people have tried to sneak a GPS in to Ranger School.

Back to graph theory. Take any set of entities and relationships between them, and you can represent the whole thing as a graph. Well, to an extent. According to the strict definition of a graph, two nodes can only be connected by at max one edge. Thus if you were representing a relationship between people, showing both family and work relationships, then it would not be possible to show that I worked for my Dad.

Graphs show up all over CS. The places they are discussed the most seem to be Networks, where the nodes are machines and the edges are network connections between them. But graphs show up in language parsing , data structures, graphics, object oriented design, databases. Graphs get hit heavily in algorithm courses as many of the most interesting problems come from graph theories.

Two basic problems in graph theory come up time and again: Minimum spanning tree and traveling salesman. Both problems assume that each edge has a weight. Minimum spanning tree attempts to connect all nodes in a graph into a tree with minimum total weight. Traveling salesman attempts to visit each node with a minimum weight path.

Let’s start with a simpler problem: shortest path. This is the problem that my GPS has to deal with when I say “Plot me a course to the Gym.” Given a weighted graph with one node designated the start node and a different node designated the end node, find the path with the least total weight.

There are several things to keep in mind. First is cycles. If your path visits the same node more than once, there exists a shorter path that visits that node only once. Note that this may not be true of driving in Boston, where you can’t take a left from Commonwealth Ave onto the BU bridge, but instead have to go another block, take a right, and loop around to cross the bridge from the south. But in a simple graph, you have to identify if you are visiting a node that you have visited before. There are two ways to do this depending on whether you are willing to spend more time or more memory on the problem. The time intensive way is to use a list, and add each node to the list. When you visit a new node, you can perform a search of the list to see if you have been there before. If so, disregard that path segment. If not, add it to the list. The alternative is to record a state in each node. When you visit the node, you check to see if the state reflects that you have already visited it. If not, mark the node as visited and continue.

That is what I can remember off the top of my head. Obviously, this is a much discussed topic. There are many Wikipedia articles on this and related topics, so I won’t attempt to reproduce that here.