Breadth First Search – BFS – Graph

Breadth first search is an algorithm for searching and traversing in a tree or graph data structures.

Below is the java implementation for Bread first Traversal.

Program

import java.util.*;
public class Main
{
    
   static class Graph{
        
        int V; 
        LinkedList<Integer> adjList[]; 
        
        Graph(int V)
        {
            this.V = V;
            adjList = new LinkedList[V];
            for(int i=0;i<V;i++)
                adjList[i] = new LinkedList();
        }
        
        void newEdge(int src, int dest)
        {
            adjList[src].add(dest);
        }
        
        void BFS(int src)
        {
           boolean visited[] = new boolean[V];
           
           LinkedList<Integer> queue = new LinkedList<Integer>();
           
           visited[src] = true;
           
           queue.add(src);
           
           while(queue.size()!=0)
           {
               src = queue.poll();
               System.out.print(src+" ");
               
               Iterator<Integer> i = adjList[src].listIterator();
               
               while(i.hasNext())
               {
                   int n = i.next();
                   
                   if(!visited[n])
                   {
                       visited[n] = true;
                       queue.add(n);
                   }
               }
           }
           
        }
        
        
    }
    
	public static void main(String[] args) {
	    
	    Graph graph = new Graph(5);
	    
	    graph.newEdge(0,1);
	    graph.newEdge(0,2);
	    graph.newEdge(1,2);
	    graph.newEdge(2,0);
	    graph.newEdge(2,3);
	    graph.newEdge(2,4);
		graph.newEdge(3,3);
		graph.newEdge(4,1);
		
		
		
		graph.BFS(1);
		
		
	}
}




Output

1 2 0 3 4

Leave a Reply

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