Graph Search. Graphs are much less uniformly structured than trees,
yet we still want to visit all their vertexes and investigate them.
There are two kinds of traversals (called searches) of graphs:
breadth-first search and depth-first search.
Breadth-first search uses a queue, while there are two versions
of depth-first search, one using a stack and one using recursion.
All these searches go from vertex
to vertex, until all reachable vertexes are visited.
In your text's notation,
all vertexes are initially "unvisited", which is denoted by
the color WHITE. As soon the program arrives at a vertex,
its color turns to GRAY, and remains GRAY until the program is
done with the vertex, when as a last act,
the program turns it BLACK.
During the course of working with a newly discovered
vertex u, the program looks at all vertices v on the adjacency
list for u. In case v is WHITE,
the edge (u, v) is added
to the growing spanning tree for the graph.
For breadth-first search, each such WHITE v is put into the queue.
For depth-first search, each WHITE v is put into the stack, or
else for each WHITE v the program calls itself recursively
from v.
Your text's Breadth-First Search Algorithm.
(See text, pages 594-602) Here is
the pseudo-code for this algorithm, which uses a queue.
This algorithm starts from a single source vertex
s and covers all vertices reachable from s.
BFS Algorithm (click picture or here for
full size image)
Here is your text's example of this search in action.
(Note that the color gray below didn't show up well,
so it has been replaced by light green.)
BFS Example (click picture or here for
full size image)
Illustrations of Breadth-First Searches.
Pictures of breadth-first search, created using Java:
BFS
Shortest Paths. Here the length of each path
is just the number of edges. You can think that the weight
of each edge is 1. (Right now we are ignoring the "distance"
weight on the edges of the US Capitals graph.)
Assume you have carried out a Breadth-First Search, starting
from vertex s. The the following algorithm (text, page 601)
prints a shortest path from s to some vertex v.
(Notice the phrase "a shortest path".
In general there may be many paths of the same length, but only
one will be specified by the spanning tree.)
Print-Path(s, v) if v == s
print s elseif v.π == NIL
print "no path from" s "to" v else Print-Path(s, v.π)
print v
This path is constructed backwards along the path
v to v.π to (v.π).π to ... to s.
Revision date:2012-10-31.
(Please use ISO 8601,
the International Standard Date and Time Notation.)
