Breadth First Search (BFS) | Iterative & Recursive Implementation

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 the neighbor nodes first, before moving to the next level neighbors.


 

Below graph shows order in which the nodes are discovered in BFS

Breadth first search (BFS) tree

 


 

Breadth first search (BFS) is a graph traversal algorithm that explores vertices in the order of their distance from the source vertex, where distance is the minimum length of a path from source vertex to the node as evident from above example.

 

Applications of BFS –

  • Copying garbage collection, Cheney’s algorithm
  • Finding the shortest path between two nodes u and v, with path length measured by number of edges (an advantage over depth first search)
  • Testing a graph for bipartiteness
  • Minimum Spanning Tree for unweighted graph
  • Web crawler
  • Finding nodes in any connected component of a graph
  • Ford–Fulkerson method for computing the maximum flow in a flow network
  • Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.

 

Iterative Implementation of BFS –

Non-recursive implementation of BFS is similar to the non-recursive implementation of DFS, but differs from it in two ways:

  • It uses a queue instead of a stack
  • It checks whether a vertex has been discovered before pushing the vertex rather than delaying this check until the vertex is dequeued from the queue

 

C++

Download   Run Code

Java

Download   Run Code



Output:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

 

Recursive Implementation of BFS –

 

C++

Download   Run Code

Java

Download   Run Code



Output:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

 

Time complexity of BFS traversal is O(n + m) where n is number of vertices and e is number of edges in the graph. Please note that O(m) may vary between O(1) and O(n2), depending on how dense the graph is.

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Rafael
Guest
Rafael

This is great code… thanks for making this so easy to understand.

Nitin
Guest
Nitin

In first program, loop should be executed from 1 to N at line #83. What if Nth node is disconnected.

Abhishek
Guest
Abhishek

https://ideone.com/6i4gd7
The second code doesn’t work for the above example .. or a disconnected graph. I think we need to put all the vertices in a loop, and call BFS from each of them, if not discovered as in
https://ideone.com/S32n6k

Wang
Guest
Wang

If it is a directed graph , we don’t need discover[] ?
since the edges will be tested only one time right?
I just want to know if my understanding right or wrong , thx in advance!

Coder
Guest
Coder

discover[] has nothing to do with the edges. It tracks vertices, which can be involved in multiple edges. Consider the directed graph a->b->c->a. If we remove discover[], nodes will be visited again and again. Also, the code will then print only one connected component of the graph.

wpDiscuz