BREADTH FIRST SEARCH IN JAVA.

/*
TOPIC: BREADTH FIRST SEARCH IN JAVA.

DATE:13/9/2012

*/

import java.io.*;
class Node
{
int element;
Node next;

Node()
{
this(0,null);
}
Node(int e,Node n)
{
element=e;
next=n;

}
int getElement()
{
return element;
}
Node getNext()
{
return next;
}
void setElement(int newEl)
{
element=newEl;
}
void setNext(Node newNext)
{
next=newNext;
}
}
class Queue
{
Node tail;
Node head;
int size;
Queue()
{
this(null,null,0);
}
Queue(Node h,Node t,int size)
{
head=h;
tail=t;
this.size=size;
System.out.println("NEW QUEUE CREATED");
}
void insert(int obj)
{
Node node=new Node();
node.setElement(obj);
node.setNext(null);
if(size==0)
head=node;
else
tail.setNext(node);
tail=node;
size++;
}
boolean isEmpty()
{
if (size==0)
return true;
else
return false;
}
int remove() throws Exception
{
int obj;
if(isEmpty())
throw new Exception("Queue is empty action prohibited");
obj=head.getElement();
head=head.getNext();
size--;
if(isEmpty())
tail=null;
return obj;
}
void display() throws Exception
{
Node q=head;
if(isEmpty())
throw new Exception("cannot display as Queue is empty");
else
{
for(int i=0;q.next!=null;i++)
{
System.out.println(q.getElement());
q=q.next;
}
}
}
void destroy()throws Exception
{
if(isEmpty())
throw new Exception("Queue is empty");
head=null;
tail=null;
size=0;
}
}

class vertex
{
int no;
boolean isv;
vertex()
{
isv=false;
}
vertex(int b)
{
no=b;
isv=false;
}
}
class graph
{
vertex vl[];
int adjm[][];
int nv=0;
Queue q;
graph()
{
System.out.println("our default size of vertex list is 20 and matrix is 20x20");
vl=new vertex[20];
adjm=new int[20][20];
for(int i=0;i<20;i++)
{
for(int j=0;j<20;j++)
{
adjm[i][j]=0;
}
}
q=new Queue();
}
void addVertex(int l)
{
vl[nv++]=new vertex(l);
}
void addEdge(int a,int b)throws Exception
{ if(a>20 || b>20)
throw new Exception("Vertex cannot be defined out of the boundary");
adjm[a][b]=1;
adjm[b][a]=1;
}
void display()
{
for (int i=0;i<nv;i++)
System.out.print(vl[i].no+" ");
}
void display(int v)
{

System.out.println(vl[v].no);
}
void bfs() throws Exception
{
vl[0].isv=true;
display (0);
q.insert(0);
int v2;
while(!q.isEmpty())
{
int v1=q.remove();
while((v2=getAdj(v1))!=-1)
{
vl[v2].isv=true;
display(v2);
q.insert(v2);
}

}
for(int i=0;i<nv;i++)
{
vl[i].isv=false;
}
}
int getAdj(int v)
{
for(int i=0;i<nv;i++)
if(v!=i)
if(adjm[v][i]==1 && vl[i].isv==false)
return i;
return -1;
}
}

class main
{
public static void main(String args[])throws Exception
{
graph g=new graph();
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
int ch;
PrintStream p=System.out;

one: for(int i=10;i>0;i++)
{
p.println();
p.println("1>INSERT VERTEX");


p.println("2>DISPLAY");
p.println("3>Breadth First Search");

p.println("4>ADD EDGE");

p.println("5>EXIT");
ch=Integer.parseInt(br.readLine());
switch (ch)
{
case 1:
int o;
p.println("enter int");
o=Integer.parseInt(br.readLine());
g.addVertex(o);
break;
case 2:
g.display();
break;
case 3:
g.bfs();
break;
case 4:
p.println("enter start vertex");
int a=Integer.parseInt(br.readLine());
p.println("enter end vertex ");
int b=Integer.parseInt(br.readLine());
g.addEdge(a,b);
break;
case 5:
g=null;
System.gc();
break one;

}
}
System.out.println("thank u coded by 6483");
}
}
/*
OUTPUT:
our default size of vertex list is 20 and matrix is 20x20
NEW QUEUE CREATED

1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
1
enter int
11

1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
1
enter int
22

1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
1
enter int
33

1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
1
enter int
44

1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
4
enter start vertex
0
enter end vertex
1

1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
4
enter start vertex
0
enter end vertex
2

1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
4
enter start vertex
1
enter end vertex
3

1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
4
enter start vertex
2
enter end vertex
3

1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
2
11      22      33      44
1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
3
11
22
33
44

1>INSERT VERTEX
2>DISPLAY
3>Breadth First Search
4>ADD EDGE
5>EXIT
5
*/