Introduction.
Please see the pages:
Graph Rep,
Complete Traversal,
and most importantly:
Breadth-First
Search.
Your text's Depth-First Search Algorithm. Here is
the pseudo-code for this algorithm, which uses recursion.
Unlike your text's BFS algorithm, this one starts from any
WHITE vertex and can handle graphs with more than one component.
We will sometimes ignore this feature when there is
a single start vertex (the "root" vertex) from which all other
vertices are reachable. Your text's topological sort
algorithm uses the more general form.
DFS Algorithm (click picture or here for
full size image)
Here is your text's example of this search in action:
DFS Example (click picture or here for
full size image)
Depth-First Search Algorithm that uses a Stack.
This algorithm is like a mash-up of the previous two algorithms,
where in place of a recursive call, the program pushes each
new WHITE vertex onto a stack.
Illustrations of Depth-First Searches.
Pictures of depth-first search, created using Java:
DFS
Revision date:2012-11-08.
(Please use ISO 8601,
the International Standard Date and Time Notation.)
