Breadth-first search (BFS) is a method for exploring a tree or graph. In a BFS, you first explore all the nodes one step away, then all the nodes two steps away, etc.

Breadth-first search is like throwing a stone in the center of a pond. The nodes you explore "ripple out" from the starting point.

It employs the following rules.

  • Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
  • Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
  • Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

Here's a how a BFS would traverse this tree, starting with the root:

                       

We'd visit all the immediate children (all the nodes that're one step away from our starting node):

                         

Then we'd move on to all those nodes' children (all the nodes that're two steps away from our starting node):

                           

And so on:

                           

 

Until we reach the end.

Breadth-first search is often compared with depth-first search.

Advantages:
  •  A BFS will find the shortest path between the starting point and any other reachable node.  A depth-first search will not necessarily find the shortest path.
Disadvantages:
  •  A BFS on a binary tree generally requires more memory than a DFS.