Graphs

In this chapter, we examine a data structure known as a graph, which can be used to represent a wide variety of data sets in which pairs of data items are related in a certain way. Examples of such data sets include road maps, data flows or control flows in programs, and representations of communication networks. Because graphs are so widely used, numerous algorithms on graphs have been devised. As a result, the same algorithm can often be applied to a variety of applications because the underlying data structure for each application is a graph.

We will begin by presenting the basic definitions and concepts, and describing the use of a data type that implements a graph. We will then examine how to use a graph to find shortest paths in a road map. We will then examine the related problem of finding shortest paths through a maze. We will conclude by discussing how to implement a graph.