Graphs are fundamental structures used in computer science to represent complex structured information. The images in Figure 6-1 are all sample graphs.
Figure 6-1. (a) House of Tudor, (b) computer network, (c) airline schedule
In this chapter we investigate common ways to represent graphs and some associated algorithms that occur frequently. Inherently, a graph contains a set of elements, known as vertices, and relationships between pairs of these elements, known as edges. In this chapter we consider only simple graphs that avoid (a) self-edges from a vertex to itself, and (b) multiple edges between the same pair of vertices.
Graphs
A graph G = (V, E) is defined by a set of vertices, V, and a set of edges, E, over pairs of these vertices. There are distinct types of graphs that occur commonly in algorithms:
Model relationships between vertices (u, v) without caring about the direction of the relationship. These graphs are useful for capturing symmetric information. For example, a road from town A to town B can be traversed in either direction.
Model relationships between vertices (u,v) that are distinct from, say, the relationship between (v, u), which may or may not exist. For example, a program to provide driving directions must store information on one-way streets to avoid giving illegal directions.