//Name:
//Roll No.:
//S.E.(comps)
//Program To Implement Bredth First Search
import java.io.*;
import java.util.*;
class Queues
{
int items[]=new int[10];
int front,rear;
Queues()
{
front=0;
rear=-1;
}
void insert(int e)
{
if(rear==9)
System.out.println("Queue Overflow");
else
items[++rear]=e;
}
boolean empty()
{
if(rear<front)
return true;
else
return false;
}
int remove()
{
return items[front++];
}
int search(int key)
{
int i=0;
while(i<10)
if(key==items[i])
return i;
else
i++;
return -1;
}
}
class BFS
{
static int v;
static int adj[][];
static boolean visited[];
public static void main(String args[])
{
Scanner read=new Scanner(System.in);
int i,j;
System.out.println("Enter the no. of vertices in the graph: ");
v=read.nextInt();
adj=new int[v+1][v+1];
visited=new boolean[v+1];
for(i=1;i<=v;i++)
{
for(j=1;j<=v;j++)
{
System.out.println("Is vertex "+j+" adjacent to vertex "+i);
System.out.println();
System.out.println("Enter 1 if yes and 0 if no");
adj[i][j]=read.nextInt();
}
}
for(i=1;i<=v;i++)
{
visited[i]=false;
System.out.println("Breadth First Search of the graph is as shown: ");
for(i=1;i<=v;i++)
{
if(visited[i]==false)
bfs(i);
}
}
}
public static void bfs(int k)
{
int j;
Queues q=new Queues();
q.insert(k);
while(!q.empty())
{
k=q.remove();
visited[k]=true;
System.out.print(k+" ");
for(j=1;j<=v;j++)
if(adj[k][j]==1)
if(visited[j]==false && q.search(j)==-1)
q.insert(j);
}
}
}
/*Output:
Enter the no. of vertices in the graph:
5
Is vertex 1 adjacent to vertex 1
Enter 1 if yes and 0 if no
1
Is vertex 2 adjacent to vertex 1
Enter 1 if yes and 0 if no
1
Is vertex 3 adjacent to vertex 1
Enter 1 if yes and 0 if no
1
Is vertex 4 adjacent to vertex 1
Enter 1 if yes and 0 if no
0
Is vertex 5 adjacent to vertex 1
Enter 1 if yes and 0 if no
0
Is vertex 1 adjacent to vertex 2
Enter 1 if yes and 0 if no
0
Is vertex 2 adjacent to vertex 2
Enter 1 if yes and 0 if no
1
Is vertex 3 adjacent to vertex 2
Enter 1 if yes and 0 if no
0
Is vertex 4 adjacent to vertex 2
Enter 1 if yes and 0 if no
1
Is vertex 5 adjacent to vertex 2
Enter 1 if yes and 0 if no
1
Is vertex 1 adjacent to vertex 3
Enter 1 if yes and 0 if no
0
Is vertex 2 adjacent to vertex 3
Enter 1 if yes and 0 if no
0
Is vertex 3 adjacent to vertex 3
Enter 1 if yes and 0 if no
1
Is vertex 4 adjacent to vertex 3
Enter 1 if yes and 0 if no
0
Is vertex 5 adjacent to vertex 3
Enter 1 if yes and 0 if no
0
Is vertex 1 adjacent to vertex 4
Enter 1 if yes and 0 if no
0
Is vertex 2 adjacent to vertex 4
Enter 1 if yes and 0 if no
0
Is vertex 3 adjacent to vertex 4
Enter 1 if yes and 0 if no
0
Is vertex 4 adjacent to vertex 4
Enter 1 if yes and 0 if no
1
Is vertex 5 adjacent to vertex 4
Enter 1 if yes and 0 if no
0
Is vertex 1 adjacent to vertex 5
Enter 1 if yes and 0 if no
0
Is vertex 2 adjacent to vertex 5
Enter 1 if yes and 0 if no
0
Is vertex 3 adjacent to vertex 5
Enter 1 if yes and 0 if no
0
Is vertex 4 adjacent to vertex 5
Enter 1 if yes and 0 if no
0
Is vertex 5 adjacent to vertex 5
Enter 1 if yes and 0 if no
1
Breadth First Search of the graph is as shown:
1 2 3 4 5
*/