Implementation

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

Implementation

Program gives the code for the BreadthFirstTraversal method of the AbstractGraph class. 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.

program50078
Program: AbstractGraph 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 10-12). Next, a new queue is created and the starting vertex is enqueued (lines 14-17).

The main loop of the BreadthFirstTraversal method comprises lines 18-30. This loop continues as long as there is a vertex in the queue and the visitor is willing to do more work (line 18). In each iteration exactly one vertex is dequeued and visited (lines 20-21). After a vertex is visited, all the successors of that node are examined (lines 22-29). 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 24-28).