Implementation

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

Implementation

Program gives the code for the breadthFirstTraversal method of the abstract Graph class. In addition to self, this method takes any Visitor and an integer. The visit method of the visitor is called once for each vertex in the graph and the vertices are visited in breadth-first traversal order starting from the vertex specified by the integer.

program50426
Program: Abstract Graph class breadthFirstTraversal method.

A bool-valued array, enqueued, is used to keep track of the vertices that have been put into the queue. The elements of the array are all initialized to False (lines 5-7). Next, a new queue is created and the starting vertex is enqueued (lines 8-9).

The main loop of the breadthFirstTraversal method comprises lines 11-17. This loop continues as long as there is a vertex in the queue and the visitor is willing to do more work (line 11). In each iteration exactly one vertex is dequeued and visited (lines 12-13). After a vertex is visited, all the successors of that node are examined (lines 14-17). Every successor of the node that has not yet been enqueued is put into the queue and the fact that it has been enqueued is recored in the array enqueued (lines 15-17).