breadth-first search

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 

A method of searching a tree that always searches one level of the tree before moving on to the next. For example, the following tree:

     A
   / | \
  B  E  F
 / \   /|\
C   D G H I

will be searched in the order ABEFCDGHI if a breadth-first search is performed on it (searching leftmost items first).

In agenda-based searching, that corresponds to the following steps:

• Add the first node to the agenda (in this case, A).
• Examine the first node on the agenda to see if it is the required item.
• Otherwise, expand the node (find all its children), and add those children to the end of the agenda.
• Repeat the second and third steps until the goal is reached.

The fact that the nodes are always added to the end of the agenda is what makes this a breadth-first search; all the siblings of a node are examined before its children are. Contrast this to depth-first search.

The advantages to breadth-first search (over depth-first search) is that it is often faster, and will always find the shortest path possible. It can also deal with looping structures without getting stuck. The disadvantage is that it takes a lot of memory, and is therefore prone to failure when all available memory is used up.

A more memory-efficient compromise between breadth-first and depth-first search is known as the iterative deepening search.