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

The breadth-first traversal   of a graph is like the breadth-first traversal of a tree discussed in Section . The breadth-first traversal of a tree visits the nodes in the order of their depth in the tree. Breadth-first tree traversal first visits all the nodes at depth zero (i.e., the root), then all the nodes at depth one, and so on.

Since a graph has no root, when we do a breadth-first traversal, we must specify the vertex at which to start the traversal. Furthermore, we can define the depth of a given vertex to be the length of the shortest path from the starting vertex to the given vertex. Thus, breadth-first traversal first visits the starting vertex, then all the vertices adjacent to the starting vertex, and the all the vertices adjacent to those, and so on.

Section  presents a non-recursive breadth-first traversal algorithm for N-ary trees that uses a queue to keep track vertices that need to be visited. The breadth-first graph traversal algorithm is very similar.

First, the starting vertex is enqueued. Then, the following steps are repeated until the queue is empty:

1. Remove the vertex at the head of the queue and call it vertex.
2. Visit vertex.
3. Follow each edge emanating from vertex to find the adjacent vertex and call it to. If to has not already been put into the queue, enqueue it.
Notice that a vertex can be put into the queue at most once. Therefore, the algorithm must somehow keep track of the vertices that have been enqueued.