Write a program to implement BFS/ DFS routine in a connected
graph
Answer / 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 |
what is best way to create a Thread class & why?
what are importance in problem tracking
In Java what is the difference between following two statements ? int a[],b; int []a,b;
please any one pass file aid,xpeditor and endeavor tools
how MATLSB software suitable for electrical branch? which tools are useful??
what is the difference between set and append?
how to hide prompts
differences between qtp10.0 and 11.0 ?
major characteristics of software system
A, B and C are 8 bit nos. They are as follows: A 1 1 0 1 1 0 1 1 B 0 1 1 1 1 0 1 0 C 0 1 1 0 1 1 0 1 Find ( (A-B) u C )=? how to solve this need with steps
Hi friends :) This Company Aptitude Questions were much easy. i have attended the interview but was not selected in the HR round. they used to ask questions like puzzles, English, fill up the sentence. for example : they asked one question like suraj, kumar, santhosh, ranga and ashwin are professionals in different fields. suraj is a doctor. kumar is not a musician.ranga is working as engineer. ashwin is from goa. santhosh is from chennai. suraj and ranga are not from delhi. find out who is working in which field and where are they from? it was not the exact question. i answered that question with correct answer. just thorough with SQL queries. they are much interested in that. i cleared Technical round where they asked me to write a C code for checking, if the given word is palindrome or not. also they asked 2 puzzle question to solve in front of them. then the asked SQL query for referring two tables. then, they sent me for HR round. i got little nervous in that round. so, could not answer them properly. In Hr round, they may ask Technical Questions. i was asked only Technical Questions in HR round. they asked questions from SQL queries and my project. i could not answer for the questions perfectly. so, i was not selected. anyway, try to be thorough with these info and rock in your interview. Thanks :)
through which algorithm does the garbage collector works? how the garbage collector will understand that the object will going to be deleted?