7. Graphs

Many problems in Computer Science and Mathematics can be reduced to a set of states and a set of transitions between these states. A graph is a mathematical representation of problems like these. In the last chapter we saw that trees serve a variety of purposes in Computer Science. Trees are graphs. However, graphs are more general than trees. Abstracting away the details of a problem and studying it in its simplest form often leads to new insight. As a result, many algorithms have come out of the research in graph theory. Graph theory was first studied by mathematicians. Many of the algorithms in graph theory are named for the mathematician that developed or discovered them. Dijkstra and Kruskal are two such mathematicians and this chapter covers algorithms developed by them.

Representing a graph can be done one of several different ways. The correct way to represent a graph depends on the algorithm being implemented. Graph theory problems include graph coloring, finding a path between two states or nodes in a graph, or finding a shortest path through a graph among many others. There are many algorithms that have come from the study of graphs. To understand the formulation of these problems it is good to learn a little graph notation which is presented in this chapter as well.

7.1. Drawing Graphs

This chapter contains several graph algorithms. Visualizing these graphs can be a challenge. Some of the pictures in the text were drawn from XML formatted files. The XML format was described in the chapter. Here are a few examples of these graph XML files.

These graphs can be drawn using turtle graphis. You can download the drawgraph.py program to draw graphs in this XML format.

There is also a very nice drawing program for Mac OS X called OmniGraffle. Most of the figures in the text were drawn with OmniGraffle. OmniGraffle saves its graphs in XML format as well. We have written a program to convert an OmniGraffle drawing of a graph to the XML format supported by the drawgraph.py program. You can download the graphreader.py program here. These programs are available As-Is for educational use. No support is provided for using them. The graphreader.py program happens to be a nice example of using dictionaries in a program.

7.2. Figures from Text

../_images/undirectedgraph.png

Fig. 1: An Undirected Graph

../_images/directedgraph.png

Fig. 2: A Directed Graph

../_images/neiowagraph.png

Fig. 3: A Weighted, Undirected Graph

../_images/graphdfs.png

Fig. 4: A Path from Vertex 0 to Vertex 1

../_images/kruskal.png

Fig. 5: A Minimum Weighted Spanning Tree

../_images/forest1.png

Fig. 6: Kruskal’s: Snapshot 1

../_images/forest2.png

Fig. 7: Kruskal’s: Snapshot 2

../_images/dijkstra.png

Fig. 8: Minimum Cost Paths and Total Cost from Source Vertex 0

../_images/weighteddirected.png

Fig. 9: A Sample Weighted, Directed Graph