        Next: Depth-First Search Up: Traversing a Graph Previous: Traversing a Graph Figure: An undirected graph and its breadth-first search tree

The basic breadth-first search algorithm is given below. At some point during the traversal, every node in the graph changes state from undiscovered to discovered. In a breadth-first search of an undirected graph, we assign a direction to each edge, from the discoverer u to the discovered v. We thus denote u to be the parent p[v]. Since each node has exactly one parent, except for the root, this defines a tree on the vertices of the graph. This tree, illustrated in Figure , defines a shortest path from the root to every other node in the tree. This property makes breadth-first search very useful in shortest path problems.

```

BFS(G,s)

for each vertex do

state[u] = ``undiscovered''

p[u] = nil, i.e. no parent is in the BFS tree

state[] = ``discovered''

p[] = nil while do

u =  dequeue[Q]

process vertex u as desired

for each do

process edge (u,v) as desired

if state[v] = ``undiscovered'' then

state[v] = ``discovered''

p[v] = u

enqueue[Q,v]

state[u] = ``completely-explored''

```

The graph edges that do not appear in the breadth-first search tree also have special properties. For undirected graphs, non-tree edges can point only to vertices on the same level as the parent vertex or to vertices on the level directly below the parent. These properties follow easily from the fact that each path in the tree must be the shortest path in the graph. For a directed graph, a back-pointing edge can exist whenever v lies closer to the root than u does.

The breadth-first search algorithm above includes places to optionally process each vertex and edge, say to copy them, print them, or count them. Each vertex and directed edge is encountered exactly once, and each undirected edge is encountered exactly twice.        Next: Depth-First Search Up: Traversing a Graph Previous: Traversing a Graph

Algorithms
Mon Jun 2 23:33:50 EDT 1997