Saturday, 20 January 2018

Java Program to traverse a Graph using BFS (Breadth First Search)

Breadth First Search (BFS) algorithm is used to traverse a graph in a breadthward motion. BFS Algorithm use data structure queue to remember to get the next vertex to start the search and we will requred an array to keep the track of vertex that it is visited or unvisited.

In BFS traversal we start the source vertex, display and mark it as visited and look for its adjacent vertices which are unvisited, display them and mark them visited and put them in the queue. If we  not found any adjacent vertex to the source node which is unvisited then, we pop out the first element of queue and do the same thing for the popped element. This steps will be repeated until the queue becomes empty. Java Program to Traverse a graph using BFS is given below

Algorithm:



1. Mark all the vertices unvisited
2. set: source=vertex from where we want to start BFS traversal
3. let vertex_status[]
       #This array is used to track that the vertex is vistied or not
4. let graph_matrix[][] is the adj_matrix of graph having n nodes
      
       #if ith and jth node is connected then graph_matrix[i][j]=1
         else graph_matrix[i][j]=0

5. Display the source vertex and mark it as visited.
6. push the sourve vertex to the Queue
7. do While Queue is not empty:
8.     set: source=queue.front
9.         Update Queue by deleting pop out front element
10.    do For i=1 to n:
11.        If graph_matrix[source][i]=1 and vertex_status[i]=unvisited:
12.                    Display vertex 'i' and mark it as visited
13.    EndFor
14. EndWhile

Example:


PROGRAM:

import java.util.*;
import java.io.*;


class Graph{

   private int n;
   private LinkedList<Integer> adj[];

   Graph(int n){
           
           this.n=n;
           this.adj=new LinkedList[n+1];
           for(int i=1;i<=n;i++){
           
             this.adj[i]=new LinkedList<Integer>();
       }
       
   }
   public void addEdge(int u,int v){

       this.adj[u].add(v);
   }
   public void b_f_s(int source){

           int sizee=this.n+1;
       boolean[] visited=new boolean[sizee];
       Queue<Integer> que=new LinkedList<Integer>();
       que.add(source);
           visited[source]=true;
           while(que.size()!=0){
                  source=que.poll();
                  System.out.print(source+" ");
                  for(int i=0;i<adj[source].size();i++){

                       if(visited[this.adj[source].get(i)]==false){
                          que.add(this.adj[source].get(i));
                          visited[this.adj[source].get(i)]=true;
                       }
                  }
           }

   }
}public class bfs{

    public static void main(String args[]){

           Scanner in=new Scanner(System.in);
           System.out.println("Enter the total number of vertices: ");
           int n=in.nextInt();
           System.out.println("Enter the number of edges: ");
           int e=in.nextInt();
           Graph graph=new Graph(n);
           System.out.println("Enter the edge source and edge destination: ");
           for(int i=0;i<e;i++){
                    int source=in.nextInt();
                    int destination=in.nextInt();
                    graph.addEdge(source,destination);

                    //Because our graph is undirected
                    graph.addEdge(destination,source);
           }
           System.out.println("Enter the source from which you want to start traversal: ");
           int source=in.nextInt();
           System.out.println("The bfs traversal of the above graph is given below: ");
           graph.b_f_s(source);
    }
}



OUTPUT:





  Click here to see C++ implementation of BFS: 





EmoticonEmoticon