Sunday 16 December 2012

BFS implementation using Java


import java.io.*;
class quelist
{
  public int front;
  public int rear;
  public int maxsize;
  public int que[];
  public quelist(int size)
  {
    maxsize = size;
    que = new int[size];
    front = rear = -1;
  }
  public void enque(int x)
  {
     if(front==-1)
     front = 0;
     que[(++rear)%maxsize]=x;
  }
  public int deque()
  {
    int temp = que[front];
    front = (front +1)%maxsize;
    return temp;
  }
   public boolean isempty()
  {
    return((front>rear)||(front==-1));
  }
}  
class vertex
{
 public char label;
 public boolean wasvisited;
 public vertex(char lab)
 {
   label = lab;
   wasvisited = false;
 }
}
class graph
{
  public final int MAX = 20;
  public int nverts;
  public int adj[][];
  public vertex vlist[];
  quelist qu;
  public graph()
  {
   nverts = 0;
   vlist = new vertex[MAX];
   adj = new int[MAX][MAX];
   qu = new quelist(MAX);
   for(int i=0;i<MAX;i++)
    for(int j=0;j<MAX;j++)
     adj[i][j] = 0;
  }
  public void addver(char lab)
  {
    vlist[nverts++] = new vertex(lab);
  }
  public void addedge(int start,int end)
  {
    adj[start][end] = 1;
    adj[end][start] = 1;
  }
  public int getadjunvis(int i)
  {
    for(int j=0;j<nverts;j++)
      if((adj[i][j]==1)&&(vlist[j].wasvisited==false))
      return j;
    return (MAX+1);  
  }
  public int getind(char l)
  {
    for(int i=0;i<nverts;i++)
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }
  public void brfs()
  {
    vlist[0].wasvisited = true;
    System.out.print(vlist[0].label);
    qu.enque(0);
    int v2;
    while(!(qu.isempty()))
    {
     int v1 = qu.deque();
     while((v2=getadjunvis(v1))!=(MAX+1))
      {
    vlist[v2].wasvisited = true;
        System.out.print(vlist[v2].label);
        qu.enque(v2);
      }  
    }
    System.out.print("\n");
  }
}



class bfs
{
  public static void main(String args[])throws IOException
  {
    graph gr = new graph();
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    System.out.println("Enter the number of vertices");
    int n = Integer.parseInt(br.readLine());
if(n<=20)
 {
System.out.println("Enter the labels for the vertices");
for(int i=0;i<n;i++)
{
 String temp = br.readLine();
 char ch = temp.charAt(0);
 gr.addver(ch);
}
System.out.println("Enter the number of edges");
int edg = Integer.parseInt(br.readLine());
System.out.println("Enter the vertices which you need to connect");
for(int j=0;j<edg;j++)
{
 System.out.println("Enter the first vertex");
 String t = br.readLine();
 char c = t.charAt(0);
 int start = gr.getind(c);

 System.out.println("Enter the second vertex");
 t = br.readLine();
 c = t.charAt(0);
 int end = gr.getind(c);

 gr.addedge(start,end);
}
System.out.print("The vertices in the graph traversed breadthwise:");
gr.brfs();
 }
 else
 {
 System.out.println("Enter the number of vertex less than 20");
 }
  }
}  

No comments:

Post a Comment

Best geography books for UPSC prelims, mains

This post is intended to clear the confusion that prevails among the aspirants over how to prepare for UPSC geography and the best books f...