Breadth First Search

posted Nov 16, 2013, 1:12 AM by Anupinder Singh   [ updated Nov 16, 2013, 1:20 AM ]
Breadth first search(BFS) is the simplest graph traversal and search algorithm. In this a given graph G=( V , E ) we start traversing the graph from on particular vertex 's' and include all nodes that are joined by an edge to vertex 's'. Once done, we then include all additional nodes that are joined by an edge to any other node previously searched for vertex 's' and we continue in the way until no new nodes are encountered. Therefore this is a layer based search and at each layer we try to discover more connecting vertices. 

Also, It computes the distance from 's' to each reachable vertex with minimum number of edges on a path joining them. Thus, BFS is not only determining the nodes that 's' can reach, but it also computing the shortest path to them. BFS also produces a tree 'T' with root 's' that contains all reachable vertices. For any vertex 'v' reachable from s, the simple path in the breadth-first tree from 's' to 'v' corresponds to a “shortest path” from 's' to 'v' in G, that is, a path containing the smallest number of edges. 

BFS algorithm works on both directed and undirected graphs.

For defining an algorithm of BFS, we assume following inputs

- Graph G =(V , E) and is represented using adjacency list.
- 's' will be denoting the source vertex(root).
- To keep track of progress, BFS color each vertex green, grey and black. All vertices start out green and later become first grey then black. So to store the color of each vertex 'u' Є 'V' in the attribute 'u.color'
- To store the predecessor of 'u' in attribute 'u.π'. In case of no predecessor it will be denoted NIL.
- To store the distance(in terms of level) attribute 'u.d' will be used. This distance will be from the root(source).
- A first-in, first-out queue 'Q' will be used to manage the grey vertices.
 
Below is the algorithm of BFS with explanation  

BFS Algo


Let us solve following example for BFS and traverse through the directed graph

BFS Example


Above example explains how the vertices color is changed and how the queue will look like when the BFS algorithm will execute as program.

Few more applications of BFS are as: 
  • Flood fill in image processing.
  • Finding all nodes within one connected component.
  • Copying collection using Cheney's algorithm.
  • Finding shortest path between two nodes (as shown in above example, it there are weights associated with each edge).
  • Testing a graph for bipartiteness. etc.