6.9 BFS & DFS

Program Definition:
A Program for implementation of BFS and DFS for a given graph
Algorithm
#include
#include
#include
#include
#define max 10
class graph
{
public:
int array[max][max],stack[max],queue[max],order[max],visited[max];
int top,rear,front,ord,vertices;
void init();
void input();
void addq(int);
int delq();
void bfs(int);
void push(int);
int pop();
void dfs(int);
void display();
};
void graph::init()
{
int i;
for(i=0;i {
visited[i]=0;
order[i]=0;
}
front=rear=-1;
top=-1;
ord=0;
}
void graph::input()
{
int i,j;
cout<<"\n enter no of vertices:";
cin>>vertices;
for(i=0;i {
for(j=0;j {
cout<<"\n enter path from"< cin>>array[i][j];
}
}
}
void graph::addq(int item)
{
if(rear==max-1)
cout<<"overflow";
else
{
queue[++rear]=item;
if(front==-1)
front=0;
}
}
int graph::delq()
{
int item;
if(front==-1)
cout<<"underflow";
else
{
item=queue[front];
if(front==rear)
front=rear=-1;
else
front=front+1;
}
return item;
}
void graph::bfs(int start)
{
visited[start]=1;
addq(start);
while(front!=-1)
{
start=delq();
for(int i=0;i<=vertices;i++)
{
if(visited[i]==0)
{
addq(i);
visited[i]=1;
order[ord++]=i;
}
}
}
}
void graph::push(int item)
{
if(top==max)
cout<<"overflow";
else
stack[++top]=item;
}
int graph::pop()
{
int item;
if(top==-1)
cout<<"underflow";
else
item=stack[top--];
return item;
}
void graph::dfs(int start)
{
visited[start]=1;
push(start);
order[ord++]=start+1;
while(top!=-1)
{
start=pop();
for(int i=0;i {
if(array[start][i] && !visited[i])
{
push(i);
dfs(i);
}
}
}
}
void graph::display()
{
cout<<"\nvisited vertices";
for(int i=0;i {
if(i)
cout<<"->";
cout< }
}
void main()
{
graph g;
int ch,ver;
clrscr();
while(1)
{
cout< cout<<"enter choice:";
cin>>ch;
switch(ch)
{
case 1:
g.init();
g.input();
break;
7 case 2:cout<<"bfs start value:";
cin>>ver;
g.init();
g.bfs(ver-1);
break;
case 3:cout<<"dfs start value:";
cin>>ver;
g.init();
g.dfs(ver-1);
break;

case 4:g.display();
break;
case 5:exit(0); } }}
Output of BFS & DFS
enter path from1to11/0 :0
enter path from1to21/0 :1
enter path from1to31/0 :1
enter path from1to41/0 :0
enter path from2to11/0 :1
enter path from2to21/0 :0
enter path from2to31/0 :0
enter path from2to41/0 :1
enter path from3to11/0 :1
enter path from3to21/0 :0
enter path from3to31/0 :0
enter path from3to41/0 :1
enter path from4to11/0 :0
enter path from4to21/0 :1
enter path from4to31/0 :1
enter path from4to41/0 :0
1.initialise 2.bfs 3.dfs 4.display 5.exit
enter choice:2
bfs start value:1
1.initialise 2.bfs 3.dfs 4.display 5.exit
enter choice:4
visited vertices1->2->3->4
1.initialise 2.bfs 3.dfs 4.display 5.exit
enter choice:3