ALLInterview.com :: Home Page            
 Advertise your Business Here     
Browse  |   Placement Papers  |   Company  |   Code Snippets  |   Certifications  |   Visa Questions
Post Question  |   Post Answer  |   My Panel  |   Search  |   Articles  |   Topics  |   ERRORS new
   Refer this Site  Refer This Site to Your Friends  Site Map  Bookmark this Site  Set it as your HomePage  Contact Us     Login  |  Sign Up                      
Google
   
 
Categories >> Software >> Programming Languages >> Programming Languages AllOther
 
 


 

 
 C interview questions  C Interview Questions (2248)
 C++ interview questions  C++ Interview Questions (1106)
 VC++ interview questions  VC++ Interview Questions (342)
 Delphi interview questions  Delphi Interview Questions (510)
 Programming Languages AllOther interview questions  Programming Languages AllOther Interview Questions (644)
Question
Write a program to implement BFS/ DFS routine in a connected
graph
 Question Submitted By :: Tanuja Panda
I also faced this Question!!     Rank Answer Posted By  
 
  Re: Write a program to implement BFS/ DFS routine in a connected graph
Answer
# 1
#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 ?    20 Yes 12 No
Akshay P
 

 
 
 
Other Programming Languages AllOther Interview Questions
 
  Question Asked @ Answers
 
What is Partial class and its use?   1
73. How can you set the status and title for a modal dialog box? a) In the attributes of the corresponding screen. b) Before the corresp. call screen statement. c) In a PBO module of the corresponding screen. d) In the PAI module of the corresponding screen.   1
1. What is the effect of the OPTIONS statement ERRORS=1? 2. What’s the difference between VAR A1 - A4 and VAR A1 — A4? 3. What do the SAS log messages "numeric values have been converted to character" mean? 4. What are the implications? 5. Why is a STOP statement needed for the POINT= option on a SET statement? 6. How do you control the number of observations and/or variables read or written? Approximately what date is represented by the SAS date value of 730? 7. How would you remove a format that has been permanently associated with a variable?? 8. What does the RUN statement do? 9. Why is SAS considered self-documenting? 10. What areas of SAS are you most interested in? 11. Briefly describe 5 ways to do a "table lookup" in SAS. 12. What versions of SAS have you used (on which platforms)? 13. What are some good SAS programming practices for processing very large data sets? 14. What are some problems you might encounter in processing missing values? In Data steps? Arithmetic? Comparisons? Functions? Classifying data? 15. How would you create a data set with 1 observation and 30 variables from a data set with 30 observations and 1 variable? 16. What is the different between functions and PROCs that calculate the same simple descriptive statistics? 17. If you were told to create many records from one record, show how you would do this using arrays and with PROC TRANSPOSE? 18. What are _numeric_ and _character_ and what do they do? 19. How would you create multiple observations from a single observation? 20. For what purpose would you use the RETAIN statement? 21. What is a method for assigning first.VAR and last.VAR to the BY group variable on unsorted data? 22. What is the order of application for output data set options, input data set options and SAS statements? 23. What is the order of evaluation of the comparison operators: + - * / ** ( ) ? 24. How could you generate test data with no input data? 25. How do you debug and test your SAS programs? 26. What can you learn from the SAS log when debugging? 27. What is the purpose of _error_? 28. How can you put a "trace" in your program? 29. Are you sensitive to code walk-throughs, peer review, or QC review? 30. Have you ever used the SAS Debugger? 31. What other SAS features do you use for error trapping and data validation? 32. How does SAS handle missing values in: assignment statements, functions, a merge, an update, sort order, formats, PROCs? 33. How many missing values are available? When might you use them? 34. How do you test for missing values? 35. How are numeric and character missing values represented internally? 36. This entry was posted in General. Bookmark the permalink. Post a comment or leave 37. How to do user inputs and command line arguments in SAS? D&B 38. How to convert a given date value into SAS date 39. How do i read multiple spaces in datasets? SAS 2
Which tag is used to create table row   2
differenc between visual studio 2005,2008 & 2010?   2
Crystal report proffessional 9 to filter the issue date!!   1
what is encapulation? Syntel 4
Why we use NEW operator when we create Object,While in C++ we donot ?   1
6.int x=10; float y=20; a=x%2=? b=y%2=?   1
What are the limitation in using querystring in .net? Tesco 1
what is runtime exception and compiletime exception ? Accenture 1
How to swap values between two variables without using a third variable? TCS 24
 
For more Programming Languages AllOther Interview Questions Click Here 
 
 
 
 
 


   
Copyright Policy  |  Terms of Service  |  Articles  |  Site Map  |  RSS Site Map  |  Contact Us
   
Copyright © 2013  ALLInterview.com.  All Rights Reserved.

ALLInterview.com   ::  KalAajKal.com