Algorithms in a Nutshell

(^138) | Chapter 6: Graph Algorithms
If a path exists between any two pairs of vertices in a graph, then that graph is
connected. A directed, weighted graph defines a nonempty set of vertices {v 0 ,...,
vn–1}, a set of directed edges between pairs of distinct vertices (such that every
pair has at most one edge between them in each direction), and a positive weight
associated with each edge. In many applications, the weight is considered to be a
distance or cost. For some applications, we may want to relax the restriction that
the weight must be positive (for example, a negative weight could reflect a profit),
but we will be careful to declare when this happens.
Consider the directed, weighted graph in Figure 6-2, which is composed of six
vertices and four edges. There are two standard data structures to store such a
graph; both data structures explicitly store the weights and implicitly store the
directed edges. One could store the graph asnadjacency lists, as shown in
Figure 6-3, where each vertexvimaintains a linked list of nodes, each of which
stores the weight of the edge leading to an adjacent vertex ofvi. Thus the base
structure is a one-dimensional array of vertices in the graph. Adding an edge
requires additional processing to ensure that no duplicate edges are added.
Figure 6-4 shows how to store the directed, weighted graph as ann-by-nadjacency
matrixAof integers, indexed in both dimensions by the vertices. The entryA[i][j]
stores the weight of the edge fromvitovj; whenA[i][j] = 0, there is no edge fromvito
vj. With the adjacency matrix representation, adding an edge takes constant time.
We can use adjacency lists and matrices to store undirected graphs as well. Consider
the undirected graph in Figure 6-5. We use the notation <v 0 ,v 1 ,...,vk–1> to describe
a path ofkvertices in a graph that traversesk–1 edges (vi,vi+1) for 0≤i<k–1; paths in a
directed graph honor the direction of the edge. In Figure 6-5, the path <v 3 ,v 1 ,v 5 ,v 4 >
is valid. In this graph there is acycle, which is a path of vertices that includes the
same vertex multiple times. A cycle is typically represented in its most minimal form.
Figure 6-2. Sample directed, weighted graph
Figure 6-3. Adjacency list representation of directed, weighted graph
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use