Implementation

Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Implementation

Program gives the code for the depthFirstTraversal method of the abstract Graph class. In addition to self, the DepthFirstTraversal 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.

program50206
Program: Abstract Graph 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 5-7). After initializing the array, the depthFirstTraversal method calls the recursive _depthFirstTraversal method. passing it the array as the third argument.

The recursive _depthFirstTraversal emthod 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.