next up previous contents index Search
Next: Euler Cycles Up: 0.4.2 Graph Traversal Previous: References Breadth-first traversal

Like a depth-first traversal, breadth-first traversal algorithms visit each node in a connected graph. However, when a breadth-first traversal arrives at a certain node, v, it visits all neighbors of node v before continuing to process other, more distant, parts of the graph. Whereas a depth first traversal can be implemented recursively, a breadth-first search is not naturally recursive. Instead of using a stack data structure, breadth-first traversal usually makes use of a queue. A queue is much like a line of people; it operates on a FIFO (first in first out) or ``first come, first served'' principle.    

The actual traversal procedure begins by enqueueing the starting node. Then the following process repeats:

  • Dequeue a current node
  • Enqueue all non-visited nodes adjacent to the current node
  • Mark non-visited nodes adjacent to the current node visited

The above cycle repeats until the queue becomes empty.

void bf_traverse (int vertex) {
  link t;

Scott Gasch