|
Greek mythology tells of an elaborate labyrinth that was built to house the monstrous part bull, part man Minotaur. This labyrinth was so complex that neither beast nor human could escape it. No human, that is, until the Greek hero, Theseus, with the help of the king's daughter, Ariadne, decided to implement one of the algorithms discussed in this chapter. Theseus fastened a ball of thread to the door of the labyrinth and unwound it as he traversed the twisting passages in search of the monster. Theseus obviously knew about good algorithm design, for, after finding and defeating the beast, Theseus easily followed the string back out of the labyrinth to the loving arms of Ariadne. Being able to determine which objects, such as labyrinth passages, are connected to which other objects may not always be as vitally important as it was in this story, but it is nevertheless fundamental. Connectivity information is present, for example, in city maps, where the objects are roads, and also in the routing tables for the Internet, where the objects are computers. Connectivity information is also present in the parent-child relationships defined by a binary tree, where the objects are tree nodes. Indeed, connectivity information can be defined by all kinds of relationships that exist between pairs of objects. The topic we study in this chapter--graphs--is therefore focused on representations and algorithms for dealing efficiently with such relationships. That is, a graph is a set of objects, called vertices, together with a collection of pairwise connections between them. By the way, this notion of a `graph' should not be confused with bar charts and function plots, as these kinds of `graphs' are unrelated to the topic of this chapter. Graphs have applications in a host of different domains, including mapping (in geographic information systems), transportation (in road and flight networks), electrical engineering (in circuits), and computer networking (in the connections of the Internet). Because applications for graphs are so widespread and diverse, people have developed a great deal of terminology to describe different components and properties of graphs. Fortunately, since most graph applications are relatively recent developments, this terminology is fairly intuitive. We therefore begin this chapter by reviewing much of this terminology and presenting the graph ADT, including some elementary properties of graphs. Having given the graph ADT, we then present, three main data structures for representing graphs. As with trees, traversals are important computations for graphs, and we discuss such computations. We discuss directed graphs, as well, where relationships have a given direction. This topic is not addressed in subsequent sections, however, so readers or instructors with limited time may skip this section. In the subsequent sections, we discuss weighted graphs, where connections have a cost or distance associated with them. While weighted connections could be directed, in these sections we study the well-known shortest path and minimum spanning tree problems for undirected graphs. |