In this chapter, we study two representations of graphs and basic algorithms on these representations.
Mathematically, a (directed) graph is a pair where is a set of vertices and is a set of ordered pairs of vertices called edges. An edge is directed from to ; is called the source of the edge and is called the target. A path in is a sequence of vertices such that, for every , the edge is in . A path is a cycle if, additionally, the edge is in . A path (or cycle) is simple if all of its vertices are unique. If there is a path from some vertex to some vertex then we say that is reachable from . An example of a graph is shown in Figure 12.1.
|
Graphs have an enormous number of applications, due to their ability to model so many phenomena. There are many obvious examples. Computer networks can be modelled as graphs, with vertices corresponding to computers and edges corresponding to (directed) communication links between those computers. Street networks can be modelled as graphs, with vertices representing intersections and edges representing streets joining consecutive intersections.
Less obvious examples occur as soon as we realize that graphs can model any pairwise relationships within a set. For example, in a university setting we might have a timetable conflict graph whose vertices represent courses offered in the university and in which the edge is present if and only if there is at least one student that is taking both class and class . Thus, an edge indicates that the exam for class can not be scheduled at the same time as the exam for class .
Throughout this section, we will use to denote the number of vertices of and to denote the number of edges of . That is, and . Furthermore, we will assume that . Any other data that we would like to associate with the elements of can be stored in an array of length .
Some typical operations performed on graphs are:
Note that these operations are not terribly difficult to implement efficiently. For example, the first three operations can be implemented directly by using a USet, so they can be implemented in constant expected time using the hash tables discussed in Chapter 5. The last two operations can be implemented in constant time by storing, for each vertex, a list of its adjacent vertices.
However, different applications of graphs have different performance requirements for these operations and, ideally, we can use the simplest implementation that satisfies all the application's requirements. For this reason, we discuss two broad categories of graph representations.