Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Depth-First Traversal

The depth-first traversal   of a graph is like the depth-first traversal of a tree discussed in Section gif. A depth-first traversal of a tree always starts at the root of the tree. Since a graph has no root, when we do a depth-first traversal, we must specify the vertex at which to begin.

A depth-first traversal of a tree visits a node and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then recursively visits all the vertices adjacent to that node. The catch is that the graph may contain cycles, but the traversal must visit every vertex at most once. The solution to the problem is to keep track of the nodes that have been visited, so that the traversal does not suffer the fate of infinite recursion.

   figure49594
Figure: Depth-first traversal.

For example, Figure gif illustrates the depth-first traversal of the directed graph tex2html_wrap_inline70346 starting from vertex c. The depth-first traversal visits the nodes in the order

displaymath70872

A depth-first traversal only follows edges that lead to unvisited vertices. As shown in Figure gif, if we omit the edges that are not followed, the remaining edges form a tree. Clearly, the depth-first traversal of this tree is equivalent to the depth-first traversal of the graph




next up previous contents index

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