Coders Packet

Implementation of Breadth-First-Search (BFS) algorithm using Java

By Abhishek Birendra Verma

In this tutorial, we will learn about the Breadth-first-Search algorithm and we will also see the program to implement the Breadth-first-Search algorithm using Java.

 

Breadth-first search (BFS) is an algorithm that is used for traversing or searching the tree or graph. The data structure used in BFS is "queue". So basically this algorithm uses two queues. The first queue contains the node(s) that are yet to be processed and the second queue contains the node(s) that are processed and deleted from the first queue. It starts from the root node or some arbitrary node of the graph and explores all the neighboring nodes in the present depth. It then explores the closest adjacent node and then explores all the unexplored nodes. The algorithm follows this process until all the nodes are explored or it reaches the destination node.

 

For the above graph, consider Q1 and Q2 as the two queues to be used for BFS.

Initially, 0 will be added in Q1 and Q2 will be empty.

Q1: 0

Q2: (empty)

Now all the neighbors of 0 will be added in Q1 and 0 will be removed from Q1 and added to Q2.

Q1: 1,2,3

Q2:0

Now all unvisited neighbors of 1 will be added in Q1 and 1 will be removed from Q1 and added to Q2.

Q1:2,3,4,5

Q2:0,1

Now all unvisited neighbors of 2 will be added in Q1 and 2 will be removed from Q1 and added to Q2.

Q1:3,4,5,6,7

Q2:0,1,2

As there is no neighbor of 3 that has not been visited yet, so 3 will be removed from Q1 and added to Q2.

Q1:4,5,6,7

Q2:0,1,2,3

 

Now as all nodes of the graph have been visited, so no new node will be added to Q1 and all the nodes in Q1 will be removed one by one and will be added to Q2. So, at the end the queues will look like this:

Q1: (empty)

Q2:0,1,2,3,4,5,6,7

 

import java.util.*;
public class BFS {

  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    Queue queue1=new LinkedList();
    Queue queue2=new LinkedList();
    System.out.print("Enter the total number of vertices in the graph: ");
    int vertices=sc.nextInt();
    boolean visited[]=new boolean[vertices];
    int adj[][]=new int[vertices][vertices],i,j,temp=0;
    for(i=0;i<vertices;i++) {
      
      for(j=0;j<vertices;j++) {
        System.out.print("Enter Adj["+(i+1)+"]["+(j+1)+"]:");
        adj[i][j]=sc.nextInt();
      }
    }
    System.out.print("Enter the Starting vertex:");
    i=sc.nextInt()-1;
    if(i<0||i>=vertices) {
      //Exiting if starting vertex is not present in the graph
      System.out.println("Incorect value!! Try again");
      System.exit(1);
    }
      
    queue1.add(i);
    visited[i]=true;
    
    while(!queue1.isEmpty()) {
      //removing the first element from the queue to visit its adjacent nodes
      temp=queue1.remove();
      queue2.add(temp);
      i=temp;
      System.out.println("i="+i);
        for(j=0;j<vertices;j++) {
          if(adj[i][j]!=0&&!visited[j]) {
            queue1.add(j);
            visited[j]=true;
          }
            
        }	
    }
    //Printing the BFS traversal of the inputted graph
    System.out.println("The Breadth First Search(BFS) of the given graph is:");
    for(i=0;i<vertices-1;i++) {
      System.out.print(queue2.remove()+1+"-->");
    }
    System.out.print(queue2.remove()+1);
  }

}

 

Download project

Reviews Report

Submitted by Abhishek Birendra Verma (AbhishekVerma)

Download packets of source code on Coders Packet