0.4.2.2 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;
|
Search