breadth-first search (idea)

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