Breadth-First Search

  • Describe the Breadth-First Search algorithm.

According to the Dictionary of Algorithms and Data Structures:

Breadth-First Search, or BFS, is any search algorithm that considers neighbors of a vertex, that is, outgoing edges of the vertex's predecessor in the search, before any outgoing edges of the vertex. Extremes are searched last.

Given a "source" vertex to initiate the search, BFS starts by visiting its adjacent nodes. All nodes can be reached by a path from the start node containing two edges, three edges, etc.

The BFS algorithm visits all vertices in a graph $G$ that are $k$ edges away from the source vertex $s$ before visiting any vertex $k+1$ edges away. You have seen this behavior in level-order tree traversal.

The process is further elaborated using a demo:

Demo

The following animated visualization of the BFS algorithm (made by Gerry Jenkins) does a good job of illustrating its behavior:

Resources