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

Implementation

Program gif gives the code for the depthFirstTraversal method of the AbstractGraph class. In fact, two depthFirstTraversal methods are defined. One of them accepts two arguments; the other, three. As indicated in Program gif, the two-argument method is declared public whereas the three-argument one is private.

The user of the Graph interface only sees the two-argument depthFirstTraversal method. This method takes any PrePostVisitor and an integer. The idea is that the visit method of the visitor is called once for each vertex in the graph and the vertices are visited in depth-first traversal order starting from the vertex specified by the integer.

   program49650
Program: AbstractGraph class depthFirstTraversal method.

In order to ensure that each vertex is visited at most once, an array of length tex2html_wrap_inline70423 of boolean values called visited is used (line 12). That is, tex2html_wrap_inline70627 only if vertex i has been visited. All the array elements are initially false (lines 13-14). After initializing the array, the two-argument method calls the three-argument one, passing it the array as the third argument.

The three-argument method returns immediately if the visitor is done. Otherwise, it visits the specified node, and then it follows all the edges emanating from that node and recursively visits the adjacent vertices if those vertices have not already been visited.


next up previous contents index

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