10.1 Definitions and Representation

An undirected graph G is a pair (V, E), where V is a finite set of points called vertices and E is a finite set of edges. An edge e E is an unordered pair (u, v), where u, v V. An edge (u, v) indicates that vertices u and v are connected. Similarly, a directed graph G, is a pair (V, E), where V is the set of vertices as we just defined, but an edge (u, v) E is an ordered pair; that is, it indicates that there is a connection from u to v. Figure 10.1 illustrates an undirected and a directed graph. We use the term graph to refer to both directed and undirected graphs.

Many definitions are common to directed and undirected graphs, although certain terms have slightly different meanings for each. If (u, v) is an edge in an undirected graph, (u, v) is incident on vertices u and v. However, if a graph is directed, then edge (u, v) is incident from vertex u and is incident to vertex v. For example, in Figure 10.1(a), edge e is incident on vertices 5 and 4, but in Figure 10.1(b), edge f is incident from vertex 5 and incident to vertex 2. If (u, v) is an edge in a undirected graph G = (V, E), vertices u and v are said to be adjacent to each other. If the graph is directed, vertex v is said to be adjacent to vertex u.

A path from a vertex v to a vertex u is a sequence <v₀, v₁, v₂, ..., v_k> of vertices where v₀ = v, v_k = u, and (v_i, v_i+1) E for i = 0, 1, ..., k - 1. The length of a path is defined as the number of edges in the path. If there exists a path from v to u, then u is reachable from v. A path is simple if all of its vertices are distinct. A path forms a cycle if its starting and ending vertices are the same - that is, v₀ = v_k. A graph with no cycles is called acyclic. A cycle is simple if all the intermediate vertices are distinct. For example, in Figure 10.1(a), the sequence <3, 6, 5, 4> is a path from vertex 3 to vertex 4, and in Figure 10.1(b) there is a directed simple cycle <1, 5, 6, 4, 1>. Additionally, in Figure 10.1(a), the sequence <1, 2, 5, 3, 6, 5, 4, 1> is an undirected cycle that is not simple because it contains the loop <5, 3, 6, 5>.

An undirected graph is connected if every pair of vertices is connected by a path. We say that a graph G^' = (V', E') is a subgraph of G = (V, E ) if V^' V and E^' E. Given a set V ^' V, the subgraph of G induced by V ' is the graph G^' = (V ', E '), where E^' = {(u, v) E|u, v V^'}. A complete graph is a graph in which each pair of vertices is adjacent. A forest is an acyclic graph, and a tree is a connected acyclic graph. Note that if G = (V, E) is a tree, then |E| = |V| - 1.

Sometimes weights are associated with each edge in E. Weights are usually real numbers representing the cost or benefit of traversing the associated edge. For example, in an electronic circuit a resistor can be represented by an edge whose weight is its resistance. A graph that has weights associated with each edge is called a weighted graph and is denoted by G = (V, E, w), where V and E are as we just defined and w : E is a real-valued function defined on E. The weight of a graph is defined as the sum of the weights of its edges. The weight of a path is the sum of the weights of its edges.

There are two standard methods for representing a graph in a computer program. The first method is to use a matrix, and the second method is to use a linked list.

Consider a graph G = (V, E) with n vertices numbered 1, 2, ..., n. The adjacency matrix of this graph is an n x n array A = (a_i, j), which is defined as follows:

Figure 10.2 illustrates an adjacency matrix representation of an undirected graph. Note that the adjacency matrix of an undirected graph is symmetric. The adjacency matrix representation can be modified to facilitate weighted graphs. In this case, A = (a_i,j) is defined as follows:

We refer to this modified adjacency matrix as the weighted adjacency matrix. The space required to store the adjacency matrix of a graph with n vertices is Q(n²).

The adjacency list representation of a graph G = (V, E ) consists of an array Adj[1..|V|] of lists. For each v V, Adj [v] is a linked list of all vertices u such that G contains an edge (v, u) E. In other words, Adj [v] is a list of all vertices adjacent to v. Figure 10.3 shows an example of the adjacency list representation. The adjacency list representation can be modified to accommodate weighted graphs by storing the weight of each edge (v, u) E in the adjacency list of vertex v. The space required to store the adjacency list is Q(|E|).

The nature of the graph determines which representation should be used. A graph G = (V, E ) is sparse if |E| is much smaller than O (|V|²); otherwise it is dense. The adjacency matrix representation is useful for dense graphs, and the adjacency list representation is often more efficient for sparse graphs. Note that the sequential run time of an algorithm using an adjacency matrix and needing to traverse all the edges of the graph is bounded below by W(|V|²) because the entire array must be accessed. However, if the adjacency list representation is used, the run time is bounded below by W(|V| + |E|) for the same reason. Thus, if the graph is sparse (|E| is much smaller than |V|²), the adjacency list representation is better than the adjacency matrix representation.

The rest of this chapter presents several graph algorithms. The first four sections present algorithms for dense graphs, and the last section discusses algorithms for sparse graphs. We assume that dense graphs are represented by an adjacency matrix, and sparse graphs by an adjacency list. Throughout this chapter, n denotes the number of vertices in the graph.