display | more...
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