Breadth First Search (BFS) Java Program

Here you will get Breadth First Search (BFS) Java program along with example.

Breadth First Search is graph traversal algorithm which has many applications in most of the algorithms. We will start with one node and we will explore all the nodes (neighbor nodes) in the same level. Then we should go to next level to explore all nodes in that level. Here BFS should fallow the graph traversal rule that it should visit each node exactly once.

Also Read: Depth First Search (DFS) Java Program

BFS uses Queue data structure to impose rule on traversing that first discovered node should be explored first.

Trees won’t have cycles. So no need to keep track of visited nodes. But in case of graph cycles will present. We may visit already visited node so we should keep track of visited node.

Breadth First Search (BFS) Example

Here we are having a graph with 6 vertices.

Now we will see how BFS will explore the vertices.

Step1: start with one node of graph. Add that node to the queue.

Breadth First Search (BFS) 1

Step2: Remove the node from queue and add the children to the queue. Here C, E are the children of A. Add elements C, E to the queue. Now A is explored but E, C are just discovered.

Breadth First Search (BFS) 2

Step 3: In queue next element is C. We should explore C first. Now remove C from queue and add it’s children to the queue.

Breadth First Search (BFS) 3

Step 4:  Now C is explored. Next element in queue is E. Add E children to queue and remove E from queue.

Breadth First Search (BFS) 4

Step 5: Next node in queue is B. No children are there so it will print the element and B will be removed from queue.

Breadth First Search (BFS) 5

Step 6: next element in queue is D. As D doesn’t have any children it will print D and D will be removed form queue.

Breadth First Search (BFS) 6

Step 7: Next element in queue is F. It doesn’t have any children so it will print and removed form queue.

Breadth First Search (BFS) 7

This way we should explore all vertices in BFS.

If in case of disconnected graph we should keep track of unvisited nodes so that we can call again BFS on that node.

Now we see the program for breadth first search in Java which will work on disconnected components also.

Breadth First Search (BFS) Java Program

Output

BFS of graph is:
0 1 9 2 3 4 5 6 7 8

Applications of Breadth First Search

  1. Finding minimum spanning tree.
  2. Shortest path finding.
  3. In networks BFS will be used for finding all neighboring nodes.
  4. In Navigation systems BFS will be useful for finding neighboring locations.
  5. Parsing social networking graphs.
  6. In garbage collection also BFS will be useful.
  7. To find connected components we can use BFS also.
  8. For crawling the search engines also it will be useful.

Comment below if you have queries or found any information incorrect in above breadth first search Java program.

Leave a Reply

Your email address will not be published. Required fields are marked *