Breadth First Search

Fig . Animation of BFS traversal of a graph

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

 In breadth-first search (BFS), we start at a particular vertex and explore all of its neighbours at the present depth before moving on to the vertices in the next level. Unlike trees, graphs can contain cycles (a path where the first and last vertices are the same). Hence, we have to keep track of the visited vertices. When implementing BFS, we use a queue data structure.

Figure  denotes the animation of a BFS traversal of an example graph. Note how vertices are discovered (yellow) and get visited (red).

The time complexity can be expressed as ${\displaystyle O(|V|+|E|)}$, since every vertex and every edge will be explored in the worst case. ${\displaystyle |V|}$ is the number of vertices and ${\displaystyle |E|}$ is the number of edges in the graph.

When the number of vertices in the graph is known ahead of time, and additional data structures are used to determine which vertices have already been added to the queue, the space complexity can be expressed as ${\displaystyle O(|V|)}$, where ${\displaystyle |V|}$ is the number of vertices

Pseudo Code:

Input: A graph G and a starting vertex root of G

Output: Goal state. The parent links trace the shortest path back to root

 1  procedure BFS(G, root) is
 2      let Q be a queue
 3      label root as discovered
 4      Q.enqueue(root)
 5      while Q is not empty do
 6          v := Q.dequeue()
 7          if v is the goal then
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10              if w is not labeled as discovered then
11                  label w as discovered
12                  Q.enqueue(w)

Applications

·        Used to determine the shortest paths and minimum spanning trees.

·        Used by search engine crawlers to build indexes of web pages.

·        Used to search on social networks.

·        Used to find available neighbour nodes in peer-to-peer networks such as BitTorrent.