Depth First Search and Breadth First Search using C++
#include<iostream>
#include<stdlib.h>
using namespace std;
char goal;
void create();
void dfs();
void bfs();
struct node
{ char data;
int status;
struct node *next;
struct link *adj;
}*start,*p,*q;
struct link
{
struct node *next;
struct link *adj;
}*l,*k;
void create()
{ char dat;
int flag=0,n;
start=NULL;
cout<<"Enter the number of nodes:";
cin>>n;
cout<<"Enter the nodes in the graph:";
for(int i=1;i<=n;i++)
{
cin>>dat;
p=new node;
p->data=dat;
p->status=0;
p->next=NULL;
p->adj=NULL;
if(flag==0)
{
start=p;
q=p;
flag++;
}
else
{
q->next=p;
q=p;
}
}
p=start;
while(p!=NULL)
{ cout<<"Enter the link to "<<p->data<<" (z to stop)";
flag=0;
while(1)
{
cin>>dat;
if(dat=='z')
break;
k=new link;
k->adj=NULL;
if(flag==0)
{
p->adj=k;
l=k;
flag++;
}
else
{
l->adj=k;
l=k;
}
q=start;
while(q!=NULL)
{
if(q->data==dat)
k->next=q;
q=q->next;
}
}
p=p->next;
}
cout<<"Enter the goal state:";
cin>>goal;
return;
}
void bfs(char goal)
{
char qu[20];
int i=1,j=0;
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
qu[0]=p->data;
p->status=1;
while(1)
{
if(qu[j]=='0')
break;
p=start;
while(p!=NULL)
{
if(p->data==qu[j])
break;
p=p->next;
}
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
qu[i]=q->data;
q->status=1;
qu[i+1]='0';
i++;
}
k=k->adj;
}
j++;
}
j=0;
cout<<"Breadth first search result: ";
while(qu[j]!='0')
{
cout<<qu[j]<<" ";
if(qu[j]==goal)
break;
j++;
}
cout<<endl;
return;
}
void dfs(char goal)
{
char stack[25];
int top=1;
cout<<"\nDepth first search result: ";
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
stack[0]='0';
stack[top]=p->data;
p->status=1;
while(1)
{
if(stack[top]=='0')
break;
p=start;
while(p!=NULL)
{
if(p->data==stack[top])
break;
p=p->next;
}
cout<<stack[top]<<" ";
if(stack[top]==goal)
break;
top--;
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
top++;
stack[top]=q->data;
q->status=1;
}
k=k->adj;
}
}
cout<<endl;
return;}
int main()
{ int i;
create();
while(1)
{
cout<<"\nEnter your choice:\n1:DFS \n2:BFS \n3:Exit\n";
cin>>i;
switch(i)
{
case 1:dfs(goal);
break;
case 2: bfs(goal);
break;
case 3:exit(0);
default:cout<<"Please enter again";}}
return 0;
}
OUTPUT:
