Algorithms in a Nutshell

(^142) | Chapter 6: Graph Algorithms
The operations from Figure 6-6 are subdivided into several categories:
Create
A graph can be initially constructed from a set ofnvertices, and it may be
directed or undirected.load(char *)updates the graph using the vertex and
edge information stored in a data file. When a graph is undirected, adding
edge (u,v) also adds edge (v,u).
Query
One can determine whether a graph is directed, find all outgoing edges for a
given vertex, determine whether an edge exists, and determine the weight
associated with an edge. One can construct an iterator that returns the neigh-
boring edges (and their weights) for any vertex in the graph.
Update
One can add edges to, or remove edges from, the graph.
Problems
There are many problems that can be solved using graph structures. In this
chapter we will cover some of the more relevant ones, and you will have opportu-
nities to find many of your own to investigate.
Given the structure defined by the edges in a graph, many problems can be
defined in terms of the shortest path that exists between two vertices in the graph,
where the length of a path is the sum of the lengths of the edges of that path. In
the “single source shortest path” problem (see Example 6-6), one is given a
specific vertex,s, and asked to compute the shortest path to all other vertices in
the graph. The “all pairs shortest path” problem (Example 6-7) requires that the
shortest path be computed for all pairs (u,v) of vertices in the graph. Some prob-
lems seek a deeper understanding of the underlying graph structure. The
minimum spanning tree (MST) of an undirected, weighted graph is a subset of
that graph’s edges such that (a) the original set of vertices is still connected in the
MST, and (b) the sum total of the weights of the edges in the MST is minimum.
We show how to efficiently solve this problem later in this chapter, in the section
“Minimum Spanning Tree Algorithms.”
We begin by discussing ways to explore a graph. Two common approaches for
carrying out such a search are DEPTH-FIRSTSEARCHand BREADTH-FIRST
SEARCH.
Depth-First Search
Consider the maze shown on the left in Figure 6-7. After some practice, a child
can rapidly find the path that stretches from the start box labeledsto the target
box labeledt. One way to solve this problem is to make as much forward progress
as possible and assume that you are not far from the target location. That is,
randomlyselect a direction whenever a choice is possible and stridently set off in that
direction, marking where you have come from. If you ever reach a dead end or you
can make no further progress without revisiting ground you have already covered,
then reverse until a non-traveled branch is found and set off in that direction.
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