import java.io.*;
import java.util.Scanner;
class Queue
{
int items[]=new int[10];
int front,rear;
Queue()
{
front=0;
rear=-1;
}
void Insert(int e)
{
if(rear==9)
System.out.println("Queue overflow");
else
items[++rear]=e;
}
int Empty()
{
return(rear<front? 1:0);
}
int Remove()
{
int x=0;
if(Empty()==1)
{
System.out.println("Queue Underflow");
return 0;
}
else
{
x=items[front++];
return x;
}
}
}
class Graph
{
int MAXSIZE=10;
int adj[][]=new int[MAXSIZE][MAXSIZE];
int visited[]=new int [MAXSIZE];
Queue q=new Queue();
void createGraph()
{
int n,i,j,parent,adj_parent,initial_node;
int ans=0,ans1=0;
System.out.print("\nEnter total number elements in a Undirected Graph :");
n=getNumber();
for (i=1;i<=n;i++)
for( j=1;j<=n;j++)
adj[i][j]=0;
for (int c=1;c<=50;c++)
visited[c]=0;
System.out.println("\nEnter graph structure for BFS ");
do
{
System.out.print("\nEnter parent node :");
parent=getNumber();
do
{
System.out.print("\nEnter adjacent node for node "+parent+ " : ");
adj_parent=getNumber();
adj[parent][adj_parent]=1;
adj[adj_parent][parent]=1;
System.out.print("\nContinue to add adjacent node for "+parent+"(1/0)?");
ans1= getNumber();
} while (ans1==1);
System.out.print("\nContinue to add graph node?");
ans= getNumber();
}while (ans ==1);
System.out.print("\nAdjacency matrix for your graph is :\n");
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
System.out.print(" "+adj[i][j]);
System.out.print("\n");
}
System.out.println("\nYour Undirected Graph is :");
for (i=1;i<=n;i++)
{
System.out.print("\nVertex "+i+"is connected to : ");
for (j=1;j<=n;j++)
{
if (adj[i][j]==1)
System.out.print(" "+j);
}
}
System.out.println("\nEnter the initial node for BFS traversal:");
initial_node=getNumber();
BFS (initial_node, n);
}
void BFS (int initial_node,int n)
{
int u,i;
u = initial_node;
visited[initial_node]=1;
System.out.println("\nBFS traversal for given graph is : ");
System.out.print(initial_node);
q.Insert(initial_node);
while(q.Empty()==0)
{
u = q.Remove();
for (i=1;i<=n;i++)
{
if((adj[u][i]==1) && (visited[i]==0))
{
q.Insert(i);
visited[i]=1;
System.out.print(" "+i);
}
}
}
}
int getNumber()
{
int ne=0;
Scanner in = new Scanner(System.in);
ne=in.nextInt();
return ne;
}
}
public class BFS
{
public static void main(String args[])
{
Graph g=new Graph();
g.createGraph();
}
}