Breadth-First Search

Breadth-first search (BFS) is a search technique used on undirected and directed graphs. Unlike depth-first search, where the probing is geared to plumb the depths first, breadth-first search proceeds more in the manner of a widening search in which the radius of the search is increased incrementally.

Since BFS is a search or a traversal algorithm, it may seem strange that we are covering this topic here under the umbrella of shortest paths. But as we’ll see shortly, this algorithm is directly applicable for finding the shortest paths in unweighted graphs and digraphs.

Mechanics of BFS

Breadth-first search can begin at any vertex. The vertex at which the search begins is called the root. From the root, all of its neighbors are visited. Then, the neighbors of these neighbors are visited, and so on. These visitations are done on a first-come, first-serve basis—if a vertex is visited before another vertex, then its neighbors, too, are visited before the neighbors of that other vertex. Of course, we don’t visit the same vertex twice.

In the following graph, let’s see the breadth-first search in action when it’s started on the vertex $v_1$. The vertices that are visited and the edges through which they are visited are often visualized as a tree called the breadth-first tree.

This search technique works equally well for directed and undirected graphs. For directed graphs, we explore only the outgoing edges.

The how

To visit all vertices in a first in, first out manner, all vertices that are visited are lined up in a queue as soon as they are visited.

• In each round, a vertex steps out from the queue and is served—by enqueuing all its neighbors.
• The process continues till the queue becomes empty.

An empty queue indicates that all vertices in the graph reachable from the root have been visited.

Algorithm

We define a function BreadthFirstSearch to implement a breadth-first search of the input graph $G$ starting at the root vertex $r$ ...