There are many different applications of graphs.
As a result, there are many different algorithms for manipulating them.
However, many of the different graph algorithms have in common
the characteristic that they systematically visit all the vertices in the graph.
I.e., the algorithm walks through the graph data structure
and performs some computation at each vertex in the graph.
This process of walking through the graph is called a
*graph traversal* .

While there are many different possible ways in which to systematically visit all the vertices of a graph, certain traversal methods occur frequently enough that they are given names of their own. This section presents three of them--depth-first traversal, breadth-first traversal and topological sort.

- Depth-First Traversal
- Breadth-First Traversal
- Topological Sort
- Graph Traversal Applications:

Testing for Cycles and Connectedness

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.