Breadth First Search Algorithm

//program to perform Breadth First Search Algorithm
#include
#include

class bfs
{
char vertex[10],visit[10],v;
int gptr[10][10],queue[10],rear,front;
int n,u,v1,k;

public:
bfs()
{
front=0;
rear=0;
v1=k=0;
}
void input();
void bfs_am(int);
void enqueue(int);
int dequeue();
int search(int);
void insert(int);
void disp();
};

// read input
void bfs::input()
{
cout<<"Enter the no of vertices:";
cin>>n;
if(n==0)
cout<<"Tree is empty";
else if(n==1)
cout<<"\nThere is only one vertex";
else
{
cout<<"\nEnter the vertices:";
for(int i=1;i<=n;i++)
cin>>vertex[i];
cout<<"Enter the adjacency matrix:\n";
for(i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>gptr[i][j];
cout<<"\nEnter the vertex from which the traversal begin:";
cin>>v;

//find index of the source vertex
for(i=1;i<=n;i++)
{
if(vertex[i]==v)
{
v1=i;
}
if(v1!=0)
break;
}
cout<<"Traversal from "< bfs_am(v1);
}
}

void bfs::bfs_am(int v)
{
u=v;
enqueue(u);
while(front!=0)
{
u=dequeue();
if(search(u)==0)
{
insert(u);
for(int i=1;i<=n;i++)
if(gptr[u][i]==1)
enqueue(i);
}
}
}

//insert a vetex into the queue
void bfs::enqueue(int u1)
{
if(front==0)
front=rear=1;
else
rear=rear+1;
queue[rear]=u1;
}

//retreve a vertex from the queue
int bfs::dequeue()
{
int item;
if(front==rear)
{
item=queue[front];
front=rear=0;
}
else
{
item=queue[front];
front=front+1;
}
return item;
}


//insert a vertex into the array
void bfs::insert(int u1)
{
k=k+1;
visit[k]=vertex[u1];
}

int bfs::search(int u)
{
int flag=0;
if(k>=1)
{
for(int i=1;i<=k;i++)
{
if(visit[i]==vertex[u])
flag=1;
}
}
return flag;
}




void bfs::disp()
{
if(n==1)
return;
for(int i=1;i<=n;i++)
cout<<"\t"< }

void main()
{
clrscr();
bfs b;
cout<<”BREADTH FIRST SEARCH\n-----------------------------\n”;
b.input();
b.disp();
getch();
}


OUTPUT


Enter the no of vertices:4

Enter the vertices:a b c d
Enter the adjacency matrix:
0 1 1 0
1 0 0 0
1 0 0 1
0 0 1 0

Enter the vertex from which the traversal begin:a
Traversal from a is:
a b c d