C program for BFS traversal

#include<stdio.h>
#include<stdlib.h>
#define SIZE 100
int FRONT=-1,REAR=-1;
int A[SIZE];
void enq(int);
int deq();
main()
{
 int VISIT[20],adjmat[20][20];
 int n,i,j,v=0;
 printf("Enter the no of vertices\n");
 scanf("%d",&n);
 printf("Enter adjacency matrix\n");
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
   scanf("%d",&adjmat[i][j]);
 }
 if (n<=0)
  printf("The graph is empty\n");
 else
 {
  printf("The BFS traversal is\n");
  for(i=0;i<n;i++)
  {
   VISIT[i]=0;
  }
  enq(v);
  while(FRONT!=-1 && REAR!=-1)
  {
   v=deq();
   if(VISIT[v]==0)
   {
    printf("\tv%d",v);
    VISIT[v]=1;
    for(i=0;i<n;i++)
    {
     if((adjmat[v][i]==1)&&(VISIT[i]==0))
      enq(i);
    }
   }
  }
 }
}
void enq(int n)
{
 if(REAR>=99)
  printf("Queue is full\n");
 else
 {
  if((REAR==-1)&&(FRONT==-1))
  {
   FRONT=0;REAR=0;
   A[REAR]=n;
  }
  else
  {
   REAR=REAR+1;
   A[REAR]=n;
  }
 }
}

int deq()
{
 int i;
 if((FRONT==-1)&&(REAR==-1))
 {
  printf("QUEUE IS EMPTY \n");
  return(-999);
 }
 else
 {
  i=A[FRONT];
  if(FRONT==REAR)
  {
   FRONT=-1;REAR=-1;
  }
  else
  {
   FRONT=FRONT+1;
  }
  return(i);
 }
}

Output



1 comment:

  1. I was searching everywhere for this code. You are awesome man.

    ReplyDelete