bfsapp.java

many simple java programs like classic algorithems to do search and few data structure implimentatio

import java.io.*;
import java.util.Scanner;

class Queue
{
    private final int SIZE =20;
    private int[] queArray;
    private int front;
    private int rear;
    
    public Queue()
    {
      queArray=new int[SIZE];
      front=0;
      rear=-1;
    }

    public void insert(int j)
    {
      if (rear==SIZE-1)
          rear=-1;
      queArray[++rear]=j;
    }

    public int remove()
    {
      int temp=queArray[front++];
      if(front==SIZE)
      front=0;
      return temp;
    }

    public boolean isEmpty()
    {
     return(rear+1==front||(front+SIZE-1==rear));
    }
}

class vertex
{
public String label;
public boolean wasVisited;
public vertex(String lab)
{
label=lab;
wasVisited=false;
}
}
class graph
{
private final int MAX_VERTS=20;
private vertex vertexlist[];
private int adjMat[][];
private int nVerts;
private Queue thequeue;
public graph()
{
vertexlist=new vertex[MAX_VERTS];
adjMat=new int [MAX_VERTS][MAX_VERTS];
nVerts=0;
for(int j=0;j<MAX_VERTS;j++)
for(int k=0;k<MAX_VERTS;k++)
adjMat[j][k]=0;
thequeue=new Queue();
}
public void addvertex(String lab)
{
vertexlist[nVerts++]=new vertex(lab);
}
public void addEdge(int start,int end)
{
adjMat[start][end]=1;
adjMat[end][start]=1;
}
public void displayvertex(int v)
{
System.out.print(vertexlist[v].label);
}
public void bfs()
{
vertexlist[0].wasVisited=true;
displayvertex(0);
thequeue.insert(0);
int v2;
while(!thequeue.isEmpty())
{
int v1=thequeue.remove();
while((v2=getAdjUnvisitedvertex(v1))!=-1)
{
vertexlist[v2].wasVisited=true;
displayvertex(v2);
thequeue.insert(v2);
}
}
for(int j=0;j<nVerts;j++)
vertexlist[j].wasVisited=false;
}
public int getAdjUnvisitedvertex(int v)
{
for(int j=0;j<nVerts;j++)
if(adjMat[v][j]==1&&vertexlist[j].wasVisited==false)
return j;
return -1;
}
}
class bfsapp
{
public static void main(String[]args)
{
int i,n,u,v;
String ip;

graph thegraph=new graph();
Scanner s= new Scanner(System.in);
System.out.println("\nEnter no: of vertex:");
n=s.nextInt();
System.out.println("Enter the"+n+"vertex");
for(i=0;i<n;i++)
{
ip=s.next();
thegraph.addvertex(ip);
}
System.out.println("\n\nEnter the "+(n-1)+" Edges in pairs");
for(i=0;i<n-1;i++)
{
u=s.nextInt();
v=s.nextInt();
System.out.println(" ");
thegraph.addEdge(u,v);
}
System.out.println("Visits:");
thegraph.bfs();
System.out.println();

}
}