## 10.1 Definitions and RepresentationAn 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. ## Figure 10.1. (a) An undirected graph and (b) a directed graph.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 An undirected graph is connected if every pair of vertices is connected by a path. We say that a graph G 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 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 ## Figure 10.2. An undirected graph and its adjacency matrix representation.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|). ## Figure 10.3. An undirected graph and its adjacency list representation.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| 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. |