Write a program to implement BFS/ DFS routine in a connected
graph
Answer Posted / akshay p
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
void create(); // For creating a graph
void dfs(); // For Deapth First Search(DFS) Traversal.
void bfs(); // For Breadth First Search(BFS) Traversal.
struct node // Structure for elements in the graph
{
int data,status;
struct node *next;
struct link *adj;
};
struct link // Structure for adjacency list
{
struct node *next;
struct link *adj;
};
struct node *start,*p,*q;
struct link *l,*k;
int main()
{
int choice;
clrscr();
create();
while(1)
{
cout<<"-----------------------\n\n";
cout<<"1: DFS\n\n2: BSF\n\n3: Exit\n\nEnter
your choice: \n";
cin>>choice;
switch(choice)
{
case 1:
dfs();
break;
case 2:
bfs();
break;
case 3:
exit(0);
break;
default:
cout<<"Incorrect choice!Re-enter your
choice.";
getch();
}
}
return 0;
}
void create() // Creating a graph
{
int dat,flag=0;
start=NULL;
cout<<"Enter the nodes in the graph(0 to end): ";
while(1)
{
cin>>dat;
if(dat==0)
break;
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 links to "<<p->data<<" (0 to
end) : ";
flag=0;
while(1)
{
cin>>dat;
if(dat==0)
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<<"-------------------------";
return;
}
// Deapth First Search(DFS) Traversal.
void bfs()
{
int qu[20],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 Results";
cout<<"---------------------------";
while(qu[j]!=0)
{
cout<<qu[j]<<" ";
j++;
}
getch();
return;
}
// Breadth First Search(BFS) Traversal.
void dfs()
{
int stack[25],top=1;
cout<<"Deapth First Search Results";
cout<<"---------------------------";
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]<<" ";
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;
}
}
getch();
return;
}
Is This Answer Correct ? | 22 Yes | 12 No |
Post New Answer View All Answers
What is test execution and when will we start execution please send me one example for this question
What is the use of sas software? Is sas and sap are different?
You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
What is the meaning of client-server application. The purpose of Client-Server Application. with description.
Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can?t pass the value k to any function also.
any drawback are there in mantis?
could you please tell me how to draw the calibration curve for HPLC {the software which we are using}?
< No Frames > tag is used for
I have try to write a record in a TDQ from a fle.... what are the steps to do... can anybody plz come with a solution
ok how would i do the following extract from a file i have ssns = 267907230 which are in column 7 into a separate data set then create a 2nd job step to extract from the data set created the following "fund code" which is in column 31 and is 113 into yet another data set
I want sample papers for NIC Examination. Plz send them to my mail Id das.neelam@gmail.com . Plz send it today, tomorrow i've the exam.
In project we have Documentation phase also,in that what is micro and macro designing?
in network security,how we identified threat?some one say we found threat according to it's signature,but how we get signature or pattern of the virus?
How do you pass variables forwrd to future CECI sessions
What is WEB 3.0? What are the features their in WEB3.0