Implementation

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Implementation

Program 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 , the two-argument method is declared public whereas the three-argument one is protected.

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.

program49865
Program: AbstractGraph class DepthFirstTraversal method.

In order to ensure that each vertex is visited at most once, an array of length of bool values called visited is used (line 10). That is, only if vertex i has been visited. All the array elements are initially false (lines 11-12). 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.