Breadth-first traversal

Back to Graph traversal

The breadth-first traversal is an algorithm for traversing the vertices of a graph. The BreadthFirst_GraphTraversal class provides an algorithm-object for breadth-first traversal.

Algorithm

The algorithm first pushes all the seed vertices at the back of a queue. As long as there is a vertex at the front of the queue, the algorithm marks , removes from the queue, and then pushes all the unmarked adjacent vertices of at the back of the queue.

Files

Breadth-first search module

Breadth-first traversal of a graph

Testing for breadth-first traversal