Showing posts with label bfs implementation. Show all posts
Showing posts with label bfs implementation. Show all posts

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");
  }
}

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...