BINARY SEARCH TREE-PRE,MID,POST TRAVERSAL METHODS.

/*

TOPIC: BINARY SEARCH TREE-PRE,MID,POST TRAVERSAL METHODS.
DATE:6/9/2012
*/

import java.util.*;
import java.io.*;
class Nodetype
{
      int info;
      Nodetype next,right,left,father ;
     Nodetype ()
      { //"the default info value is 03"
            this(3);

      }

 Nodetype (int i)
      {
            info = i ;
            left= null;
            right=null;
            father=null;

      }
}
class Operations
{
  Nodetype maketree(int x)
  {
    Nodetype node=new Nodetype(x);
    return(node);
  }

  void setleft(Nodetype p,int x)
  {
   if(p==null)
       System.out.println("Invalid insertion");
   else
     if(p.left!=null)
       System.out.println("Invalid insertion");
     else
       p.left=maketree(x);    
  }

   void setright(Nodetype p,int x)
  {
   if(p==null)
       System.out.println("Invalid insertion");
   else
     if(p.right!=null)
        System.out.println("Invalid insertion");
     else
        p.right=maketree(x);
     
   }
 
 

  void intrav(Nodetype ptree)
  {
    if(ptree!=null)
    { System.out.println();
       intrav(ptree.left);
       System.out.println(ptree.info+" ");
       intrav(ptree.right);
    }
  }

  void pretrav(Nodetype ptree)
  {
    if(ptree!=null)
    { System.out.println();
       System.out.println(ptree.info+" ");
       pretrav(ptree.left);
       pretrav(ptree.right);
    }
  }

  void postrav(Nodetype ptree)
  {
    if(ptree!=null)
    { System.out.println();
       postrav(ptree.left);
       postrav(ptree.right);
       System.out.println(ptree.info+" ");
    }
  }

  void create() throws Exception
  {
    BufferedReader br = new BufferedReader ( new InputStreamReader(System.in));
Nodetype ptree,p,q;
    int n,number=0;
    System.out.println(" Enter no. of nodes:");
    n=Integer.parseInt(br.readLine());
    System.out.println("enter info for"+n+" nodes:");
    number=Integer.parseInt(br.readLine());
    ptree=maketree(number);
    for(int i=1;i<n;i++)
    {
      number=Integer.parseInt(br.readLine());
      p=q=ptree;
      while(q!=null && number!=p.info)
      {
        p=q;
        if(number<p.info)
         q=p.left;
        else
         q=p.right;
      }
     if(number==p.info)
       System.out.println(number+" is duplicate");
     else
       if(number<p.info)
        setleft(p,number);
       else
        setright(p,number);
    }
    System.out.println("Inorder traversal:");
    intrav(ptree);
    System.out.println("preorder traversal: ");
    pretrav(ptree);
    System.out.println("postorder traversal: ");
    postrav(ptree);
  }

}

class Demo
{

    public static void main(String args[])throws Exception
    {
      Operations op=new Operations();
      op.create();
     System.out.println("thank u coded by TG");
}

}
/*
OUTPUT:
java Demo
 Enter no. of nodes:
13
enter info for13 nodes:
8
3
1
5
6
7
11
9
10
14
12
13
15
Inorder traversal:
1 3 5 6 7 8 9 10 11 12 13 14 15
preorder traversal:
8 3 1 5 6 7 11 9 10 14 12 13 15
postorder traversal:
1 7 6 5 3 10 9 13 12 15 14 11 8
thank u coded by TG
*/

BINARY TREE OPERATIONS-INSERT,SEARCH,DELETE,DISPLAY IN JAVA.

/*
TOPIC: BINARY TREE OPERATIONS-INSERT,SEARCH,DELETE,DISPLAY.
DATE:20/9/2012
*/
import java.util.*;
import java.io.*;
class Node
{
int data;
Node left,right;
public Node(int data)
{
 this.data=data;
 left=right=null;
}
}
class BST
{
private Node root;
public BST()
{
 root=null;
}
Node father(Node p)
{
if(p==root)
return null;
Node q=root;
while(q!=null)
{
 if(q.left==p||q.right==p)
 return q;
 if(p.data<=q.data)
 q=q.left;
 else
 q=q.right;
}
return null;
}
public Node findmax(Node r)
{
if(r.right==null)
return r;
else
return (findmax(r.left));
}
public Node findmin(Node r)
{
if(r.left==null)
return r;
else
return (findmin(r.left));
}
public void insert(int ele)
{
Node p=new Node(ele);
if(root==null)
{
 root=p;
 return;
}
Node q=root;
while(q!=null)
{
 if(p.data<=q.data)
  if(q.left==null)
  {
   q.left=p;
   break;
  }
 else q=q.left;
 else if(q.right==null)
 {
  q.right=p;
  break;
 }
 else
 q=q.right;
}
}
public void inorder(Node x)
{
if(x!=null)
{
 inorder(x.left);
 System.out.println(x.data+" ");
 inorder(x.right);
}
}
public void preorder(Node x)
{
if(x!=null)
{
 System.out.println(x.data+" ");
 preorder(x.left);
 preorder(x.right);
}
}
public void postorder(Node x)
{
if(x!=null)
 {
  postorder(x.left);
  postorder(x.right);
  System.out.println(x.data+" ");
 }
}
public Node get_root()
{
 return root;
}
boolean search(int ele)
{
Node q=root;
while(q!=null)
{
 if(q.data==ele)
 {
  System.out.println("element found");
  return true;
 }
 if(ele<q.data)
  q=q.left;
 else
  q=q.right;
}
System.out.println("element not found");
return false;
}
public void delete(int ele)
{
if(root==null)
{
 System.out.println("Tree is empty");
 return;
}
Node q=root;
while(q!=null)
{
 if(q.data==ele)
 break;
 if(ele<q.data)
 q=q.left;
 else
 q=q.right;
}
if(q==null)
{
 System.out.println("element not found");
 return;
}
if(q.left==null&&q.right==null)
{
 if(q==root)
 {
  root=null;
  return;
 }
if(father(q).left==q)
 father(q).left=null;
else
 father(q).right=null;
return;
}
if(q.left!=null)
{
 Node ptr=findmax(q.left);
 int val=ptr.data;
 delete(ptr.data);
 q.data=val;
 return;
}
if(q==root)
{
 root=root.right;
 return;
}
if(father(q).left==q)
 father(q).left=q.right;
else
 father(q).right=q.right;

}
}
class Demo
{
public static void main(String args[])
{
PrintStream p=System.out;
 int ele;
 Scanner src=new Scanner(System.in);
 p.println("Enter no of nodes to be created initially");
 int n=src.nextInt();
 BST obj=new BST();
 for(int i=0;i<n;i++)
 {
  p.println("enter data");
  ele=src.nextInt();
  obj.insert(ele);
 }
while(true)
{

p.println("1: Insert ");
p.println(" 2:Inorder");
p.println("3:Preorder");
p.println("4:Postorder");
p.println("5:DELETE");
p.println("6:SEARCH");
p.println("7:EXIT");
  int ch=src.nextInt();
  if(ch==7){p.println("
THANK U CODED BY TG");
  break;}
  switch(ch)
  {
  case 1: p.println("enter element to be inserted");
          ele=src.nextInt();
          obj.insert(ele);
          break;
  case 2: if(obj.get_root()!=null)
           obj.inorder(obj.get_root());
          else
           p.println("tree is empty");
          break;
  case 3: if(obj.get_root()!=null)
           obj.preorder(obj.get_root());
          else
           p.println("tree is empty");
          break;
  case 4: if(obj.get_root()!=null)
           obj.postorder(obj.get_root());
          else
           p.println("tree is empty");
          break;  
  case 5: if(obj.get_root()!=null)
          {
           p.println("enter the element to be deleted");
           ele=src.nextInt();
           obj.delete(ele);
          }
          else
           p.println("tree is empty");
          break;
  case 6: if(obj.get_root()!=null)
          {
           p.println("enter the element to be searched");
           ele=src.nextInt();
          obj.search(ele);
          }
          else
           p.println("tree is empty");
          break;
  }
}
}
}

/*
OUTPUT:
java Demo
Enter no of nodes to be created initially
1
enter data
10
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
5
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
30
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
25
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
40
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
27
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
1
enter element to be inserted
45
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
2
5
10
25
27
30
40
45
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
5
enter the element to be deleted
45
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
2
5
10
25
27
30
40
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
5
enter the element to be deleted
25
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
2
5
10
27
30
40
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
5
enter the element to be deleted
30
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
2
5
10
27
40
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
6
enter the element to be searched
27
element found
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
6
enter the element to be searched
100
element not found
1: Insert
 2:Inorder
3:Preorder
4:Postorder
5:DELETE
6:SEARCH
7:EXIT
7
THANK U CODED BY TG/*

MERGE SORT ALGORITHM

/*

TOPIC: MERGE SORT ALGORITHM.
DATE:4/10/2012
*/
import java.io.*;
class Sequence
{
BufferedReader br;
int a[];
int size,temp;
boolean flag;
int l1,l2,l3,k,a1,a2,i,j;
Sequence()
{
br = new BufferedReader ( new InputStreamReader(System.in));
flag=true;
}
void create()throws IOException
{
System.out.println("enter size of array: ");
size=Integer.parseInt(br.readLine());
a=new int[size];
insert();
}
void insert()throws IOException
{
System.out.println("INSERT THE ELEMENTS INTO THE ARRAY");
for(i=0;i<size;i++)
a[i]=Integer.parseInt(br.readLine());
}
void MergeSort()

{
MergeSort(0,a.length-1);
}
void MergeSort(int lo,int n)

{
int low=lo;
int high=n;
if(low>=high)
return;
int middle=(low+high)/2;
MergeSort(low,middle);
MergeSort(middle+1,high);
int end_low=middle;
int start_high=middle+1;
while((low<=end_low)&&(start_high<=high))
{
if(a[low]<a[start_high])
{
low++;
}
else{
int temp=a[start_high];
for(int k=start_high-1;k>=low;k--)
a[k+1]=a[k];
a[low]=temp;
low++;
end_low++;
start_high++;
}
}
}

void display()
{
for(i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
class MergeSort
{
public static void main(String args[])throws Exception
{
Sequence s=new Sequence();
s.create();
System.out.println("BEFORE SORTING");
s.display();
s.MergeSort();
System.out.println("AFTER SORTING");
s.display();
//System.out.println("THANK U CODED BY TG");
}
}
/*
OUTPUT:
enter size of array:
8
INSERT THE ELEMENTS INTO THE ARRAY
55
4
98
7
65
26
3
444
BEFORE SORTING
55              4               98              7               65             26               3               444
AFTER SORTING
3               4               7               26              55             65               98              444

*/

INSERTION SORT ALGORITHM IN JAVA.

/*
TOPIC: INSERTION SORT ALGORITHM IN JAVA.
DATE:19/9/2012
*/
import java.io.*;
class Sequence
{
BufferedReader br;
int a[];
int size,temp;
boolean flag;

Sequence()
{
br = new BufferedReader ( new InputStreamReader(System.in));
flag=true;
}
void create()throws IOException
{
System.out.println("enter size of array: ");
size=Integer.parseInt(br.readLine());
a=new int[size];
insert();
}
void insert()throws IOException
{
System.out.println("INSERT THE ELEMENTS INTO THE ARRAY");
for(int i=0;i<size;i++)
a[i]=Integer.parseInt(br.readLine());
}
void insertionsort()
{ int j=0;
for(int i=1;i<a.length;i++)
{
temp=a[i];
j=i;
while(j>0&&a[j-1]>=temp)
{
a[j]=a[j-1];
j--;
}
a[j]=temp;
}
System.out.println("AFTER SORTING");
display();
}

void display()
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
class insertionsort
{
public static void main(String args[])throws Exception
{
Sequence s=new Sequence();
s.create();
System.out.println("BEFORE SORTING");
s.display();
s.insertionsort();
System.out.println("THANK U CODED BY TG");
}
}
/*
OUTPUT:
enter size of array:
8
INSERT THE ELEMENTS INTO THE ARRAY
200
14
96
48
555
422
316
122
BEFORE SORTING
200             14              96              48              555             422             316             122
AFTER SORTING
14              48              96              122             200             316             422             555
THANK U CODED BY TG
*/

HEAP SORT ALGORITHM IN JAVA.

/*
TOPIC: HEAP SORT ALGORITHM.
DATE:3/10/2012
*/

import java.io.*;
class Sequence
{
int size;
int i;
int a[]=new int[25];
BufferedReader br;
Sequence()
{
br = new BufferedReader ( new InputStreamReader(System.in));
}
void create()throws IOException
{
System.out.println("enter size of array: ");
size=Integer.parseInt(br.readLine());
a=new int[size];
insert();
}
void insert()throws IOException
{
System.out.println("INSERT THE ELEMENTS INTO THE ARRAY");
for(int i=0;i<size;i++)
a[i]=Integer.parseInt(br.readLine());
}

void display()
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
void HeapSort()
{
int n=size;
int i,elt,s,f,ivalue,pass=1;
    for(i=1;i<n;i++)
    {
elt=a[i];
s=i;
f=(s-1)/2;
while((s>0)&&(a[f]<elt))
{
   a[s]=a[f];
   s=f;
   f=(s-1)/2;
}
a[s]=elt;
    }
    for(i=n-1;i>0;i--)
    {
ivalue=a[i];
a[i]=a[0];
f=0;
if(i==1)
s=-1;
else
s=1;
if((i>2)&&(a[2]>a[1]))
s=2;
while((s>=0)&&(ivalue<a[s]))
{
   a[f]=a[s];
   f=s;
   s=2*f+1;
   if((s+1<=i-1)&&(a[s]<a[s+1]))
       s=s+1;
   if(s>(i-1))
s=-1;
}
       a[f]=ivalue;
System.out.println();
    }

}
}  
class HeapSort
{
public static void main(String args[])throws IOException
{
      Sequence s=new Sequence();
s.create();
System.out.println("BEFORE SORTING:");
s.display();
    s.HeapSort();
    System.out.println("AFTER SORTING:");
 
s.display();
}

}
/*
OUTPUT:
enter size of array:
8
INSERT THE ELEMENTS INTO THE ARRAY
25
4
65
9
555
1
23
12
BEFORE SORTING:
25              4               65              9               555            23               12
AFTER SORTING:
1               4               9               12              23             25               65              555

*/

BRUTE FORCE ALGORITHM IN JAVA.

/*
TOPIC: BRUTE FORCE ALGORITHM.

DATE:11/9/2012

*/
import java.io.*;
import javax.swing.*;
class StringMatching
{
BufferedReader br;
String t,pat,mid;
int pos,i;
PrintStream p;
StringMatching()
{
p=System.out;
br=new BufferedReader(new InputStreamReader(System.in));
}
void getData()
{
p.println("Enter the TEXT STRING: ");
t=JOptionPane.showInputDialog("Enter string","");
p.println("Enter the PATTERN :");
pat=JOptionPane.showInputDialog("Enter Pattern","");
p.println("pattern is: "+pat+" text is "+t);
}
void Bruteforce()
{
for(pos=0;pos<=(t.length()-pat.length());pos++)
{
mid=t.substring(pos,pos+pat.length());
if(pat.equals(mid))
{
p.println(t);
for(i=0;i<pos;i++)

p.print(" ");
p.println(pat);
p.println();

}
}
}
public static void main(String args[])throws Exception
{
StringMatching sm=new StringMatching();
sm.getData();
sm.Bruteforce();
}
}

/*
OUTPUT:
Enter the TEXT STRING:
Enter the PATTERN :
pattern is: ll  text is hello to all
hello to all
  ll

hello to all
          ll
*/

INFIX TO POSTFIX CONVERSION USING STACK.

/*

TOPIC: INFIX TO POSTFIX.
DATE:9/8/2012

*/
import java.util.*;
import java.io.*;
class stack
{
int top;char a[];
stack(int n)
{
top=-1;
a=new char[n];
}
void push(char c)
{
if(top==a.length-1)
System.out.println("stack full");
else a[++top]=c;
}
char pop() throws Exception
{
if (top==-1) throw new Exception("stack empty");
else return a[top--];
}
boolean empty()
{
return top==-1;
}
char peek() throws Exception
{
if(empty())
throw new Exception();
else
return a[top];
}
void display() throws Exception
{
if(empty())
throw new Exception();
else
{
for(int i=0;i<+top;i++)
{
System.out.print(a[i]+" ");
}

}}
int compare(char c)
{
switch (c)
{
case '$':
case '^':return 4;
case '*':
case '/':return 3;
case '+':
case '-':return 2;
case '(':
case ')':return 1;
}
return 0;
}
}
class demo
{
public static void main(String arg[])throws Exception
{
Scanner sc=new Scanner (System.in);
stack s=new stack(10);
System.out.println("enter infix exp");
String infix=sc.next();

String post=" ";
char a[]=infix.toCharArray();
for(int i=0;i<a.length;i++)
{
if (Character.isLetterOrDigit(a[i]))
post+=a[i];
else
if(s.empty()||a[i]=='('||s.compare(a[i])>s.compare(s.peek())||a[i]=='^')
s.push(a[i]);
else if(a[i]==')')
{
while (s.peek()!='(')
post+=s.pop();
s.pop();
}

else
{
while(!s.empty()&&s.compare(a[i])>=s.compare(s.peek()))
post+=s.pop();
s.push(a[i]);
}
}
while(!s.empty())
{
post+=s.pop();
System.out.print(post);
}
}
}
/*
OUTPUT:
enter infix exp
a*(b-c)/d

abc-*d/
*/

DEPTH FIRST SEARCH IN JAVA.

/*
TOPIC: DEPTH FIRST SEARCH IN JAVA.
SEIT
DATE:13/9/2012

*/
import java.io.*;
class Stack
{
int stk[]=new int[20];
int top;
Stack()
{
top=-1;
}
void push(int i)
{
if(top==19)
System.out.println("Stack Overflow!");
else
stk[++top]=i;
}

int peek()
{
return stk[top];
}
int pop()
{
if(this.isEmpty())
{
System.out.println("underflow");
return 0;}
else
{
System.out.println(stk[top]);

return stk[top--];
}}
boolean isEmpty()
{
if(top<0)
return true;
else
return false;
}
}
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;
Stack s;
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;
}
}
s=new Stack();
}
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 dfs()
{
vl[0].isv=true;
display (0);
s.push(0);
for(int j=1;j<nv;j++)
{
int v=getAdj(s.peek());
if(v==-1)
s.pop();
else
{
vl[v].isv=true;
display (v);
s.push(v);
}
}
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>Depth 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 object");
o=Integer.parseInt(br.readLine());
g.addVertex(o);
break;
case 2:
g.display();
break;
case 3:
g.dfs();
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 TG");
}
}
/*
OUTPUT:
our default size of vertex list is 20 and matrix is 20x20

1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
1
enter object
1

1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
1
enter object
2

1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
1
enter object
3

1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
1
enter object
4

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

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

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

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

1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
2
1       2       3       4
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
3
1
2
4
3

1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
5
thank u coded by TG

*/

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
*/