136Chapter 6. Graph Algorithms......................................................................................................................................................
6
Graph Algorithms
Overview
Graphs are fundamental structures used in computer science to represent complex
structured information. The images in Figure 6-1 are all sample graphs.
In this chapter we investigate common ways to represent graphs and some associ-
ated algorithms that occur frequently. Inherently, a graph contains a set of
elements, known asvertices, and relationships between pairs of these elements,
known asedges. 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:
Undirected graphs
Model relationships between vertices (u,v) without caring about the direc-
tion 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.
Directed graphs
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.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