BFS implementation of GRAPH:
import java.util.*;
class Graph
{
int V;
LinkedList<Integer> list[];
Graph(int V)
{
this.V=V;
list=new LinkedList[V];
for(int index=0;index<V;index++)
{
list[index]=new LinkedList();
}
}
void addEdge(int v,int w)
{
list[v].add(w);
}
void BFS(int s)
{
boolean[] visited=new boolean[V];
LinkedList<Integer> queue=new LinkedList<>();
visited[s]=true;
queue.add(s);
while(queue.size()!=0)
{
s=queue.poll();
System.out.print(s+" ");
Iterator<Integer> itr=list[s].listIterator();
while(itr.hasNext())
{
int n=itr.next();
while(!visited[n])
{
visited[n]=true;
queue.add(n);
}
}
}
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the number of vertex");
int size=sc.nextInt();
Graph graph=new Graph(size);
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(1,2);
graph.addEdge(2,0);
graph.addEdge(2,3);
graph.addEdge(3,3);
System.out.println("Enter the starting vertex:");
int vertex=sc.nextInt();
System.out.println("BFS from Vertex "+vertex+":");
graph.BFS(vertex);
}
}
input 1:
Enter the number of vertex:
4
Enter the starting vertex:
1
output 1:
BFS from Vertex 1:
1 2 0 3
input 2:
Enter the number of vertex:
4
Enter the starting vertex:
0
output 2:
BFS from Vertex 1:
0 1 2 3