Breadth-First Search or BFS for a Graph Data Structure

By | July 22, 2020

In post talks about Breadth-First Search or BFS for a Graph Data Structure with example

To solve problems on graphs, we need a mechanism for traveling the graph. graph traversal algorithms are usually called Graph Search Algorithms. like trees traversal algorithms( inorder, preorder, and level order traversals), Graph Search algorithms can be thought of As starting at some source vertex in a graph and searching the graph by going through the edges and marking the vertices. We have mainly two search algorithms for traveling the graphs

In this post, we will learn how to write  a Java program for a Binary tree traversal using breadth-first search which is also known as level order traversal of binary tree

Breadth-First Search (BFS)

Contrary to the Depth-First Search(DFS) where traversal is done by moving to the node in the next level, in Breadth-First Search(BFS) all the nodes with in the same level are visited then only next level is visited.

For depth search Java program you can refer to this post- Depth-First Search or DFS for a Graph Data Structure

Breadth-First Search(BFS)

The level order traversal of the binary tree as per the above image is as follows:

 

Level 0 – 60

Level 1- 30, 70

Level 2- 25, 38, 61, 85

Level 3- 10, 28, 32

Breadth-First Search (BFS) Program can be implemented using two approaches:

  • Recursive Approach
  • Non-recursive Approach

Breadth-First Search (BFS) Recursive Approach Source Code:

To write a Java program using a recursive approach to do a level order traversal of a binary tree We need to find the height of the tree and then call method for level order traversal for level 0 to max level of the binary tree.

Breadth-First Search (BFS) Non-Recursive Approach Source Code:

To write a Java program for level order traversal of a binary tree using a non-recursive method a queue is used. Initially, the root of the tree is inserted into the queue then you need to do the following until the queue is empty.

  1. We have to poll a node from the queue and display its value.
  2. We have to check if the node has left child, if yes then add that to the queue.
  3. Finally, we have to check if the node has the right child, if yes then add that to the queue.

Below is the Complete Source code:

The Output of this Program:

Height Of Tree: 4
Level order traversal using recursive method
60 30 70 25 38 61 85 10 28 32
Level order traversal using iterative method
60 30 70 25 38 61 85 10 28 32

Advantages of BFS

A BFS can be used to find the shortest path between the starting point and any other reachable node.

Disadvantages of BFS

A Breadth-First Search(BFS) on a binary tree usually requires more memory than a DFS.

Application of BFS

Finding all connected components in a graph
Finding all nodes within one connected component
Finding the shortest path between two nodes

Comparing DFS and BFS Algorithms:

The big advantage of DFS is that it has much lower memory requirements than BFS because it’s not required to store all of the children pointers at each level. Depending on the data and what we are looking for, either DFS and BFS can be advantageous. For example in a family tree if we are looking for someone who is still alive and if we assume that person would be at the bottom of the tree then DFS is a better choice. BFS usually takes a very long time to reach that last level.

 The DFS algorithm finds the goal faster. Now if we are looking for a family member who died a very long time ago then the person would be closer to the top of the tree. In this case, BFS finds faster than the DFS. S0 the advantages of either vary depending on the data and what we are looking for. DFS is related to the preorder traversal of a tree. Like preorder traversal, DFS digits each node before its children. The BFS algorithm works similarly to the level order traversal of the trees.

 If someone asks that the DFS is better or BFS is better. The answer depends on the type of problem that they are trying to solve. BFS visits each level one at a time and if we know the solution we are searching for is at low depth then BFS is good. DFS is a better choice if the solution is maximum depth. The below table shows the difference between DFS and BFS in terms of their applications

Applications DFS BFS
Spanning forest, connected components, paths, cycles YES YES
Shortest Paths YES
Minimal use of memory space YES

 

You May Also Like:

Introduction to Graph Data Structure?
Important Types of Graph Data Structure
Breadth-First Search or BFS for a Graph Data Structure

That’s all about Breadth-First Search or BFS for a Graph Data Structure
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply

Your email address will not be published.