A

graph-traversal

strategy that visits every

vertex adjacent to a vertex v that it can before it visits any other vertex. Thus, the traversal will not

embark from any of the vertices adjacent to

* v * until it has visited all possible vertices adjacent to

* v*. See also

depth-first search.

An iterative BFS traversal algorithm uses a queue:

*BFS(v)
*

// Traverses a graph beginning at vertex v by using a

// breadth-first search: Iterative version.

Q.CreateQueue()

// add v to queue and mark it

Q.QueueInsert(v, Success)

Mark v as visited

**while** (!Q.QueueIsEmpty())

{ Q.QueueDelete(w, Success)

// loop invariant: there is a path from vertex w to

// every vertex in the queue Q

** for** (each unvisited vertex u adjacent to w)

{ Mark u as visited

Q.QueueInsert(u, Success)

} // end for

} // end while