Wednesday, October 9, 2013

BFS Program using Queue


Program:
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 display()
  {
     for(int i = front;i<=rear;i++)
         System.out.print(que[i]+"    ");
  }
 
  public void enque(int x)
  {
     if(front==-1)
     front = 0;
     que[++rear]=x;
  }

  public int deque()
  {
    int temp = que[front];
    front = front +1;
    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 void display(int i)
  {
    System.out.print(vlist[i].label);
  }

  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;
    display(0);
    qu.enque(0);
    int v2;
    while(!(qu.isempty()))
    { 
     int v1 = qu.deque();
     while((v2=getadjunvis(v1))!=(MAX+1))
      { 
    vlist[v2].wasvisited = true;
        display(v2);
        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());
    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();
  }  
}  

No comments:

Post a Comment