Search:

Submit Article

# Program of Breadth First Search Traversal ( BFS )

Posted By: Easy Tutor     Category: C++ Programming     Views: 80656

## Code for Program of Breadth First Search Traversal ( BFS ) in C++ Programming

```#include <iostream.h>
#include <conio.h>
#define MAX_NODE 50

struct node{
int vertex;
node *next;
};

node *adj[MAX_NODE]; //For storing Adjacency list of nodes.int totNodes; //No. of Nodes in Graph.////////////Queue Operation\\\\\\\\\\\\\int queue[MAX_NODE],f=-1,r=-1;

void q_insert(int item){
r = r+1;
queue[r]=item;
if(f==-1)
f=0;
}

int q_delete(){
int delitem=queue[f];
if(f==r)
f=r=-1;
else
f=f+1;
return(delitem);
}

int is_q_empty(){
if(f==-1)
return(1);
elsereturn(0);
}
////////////Queue Operation\\\\\\\\\\\\\void createGraph(){
node *newl,*last;
int neighbours,neighbour_value;
cout<<"\n\n---Graph Creation---\n\n";
cout<<"Enter total nodes in graph : ";
cin>>totNodes;
for(int i=1;i<=totNodes;i++){
last=NULL;
cout<<"\nEnter no. of nodes in the adjacency list of node "<<i<<"\n";
cout<<"--> That is Total Neighbours of "<<i<<" : ";
cin>>neighbours;
for(int j=1;j<=neighbours;j++){
cout<<"Enter neighbour #"<<j<<" : ";
cin>>neighbour_value;
newl=new node;
newl->vertex=neighbour_value;
newl->next=NULL;
else{
last->next = newl;
last = newl;
}
}
}
}

void BFS_traversal(){
node *tmp;
int N,v,start_node,status[MAX_NODE];//status arr for maintaing status.constint ready=1,wait=2,processed=3; //status of node.

cout<<"Enter starting node : ";
cin>>start_node;

//step 1 : Initialize all nodes to ready state.for(int i=1;i<=totNodes;i++)

//step 2 : put the start node in queue and change status.
q_insert(start_node); //Put starting node into queue.
status[start_node]=wait; //change it status to wait state.//step 3 : Repeat until queue is empty.while(is_q_empty()!=1){

//step 4 : Remove the front node N of queue.//process N and change the status of N to//be processed state.
N = q_delete(); //remove front node of queue.
status[N]=processed; //status of N to processed.
cout<<"   "<<N; //displaying processed node.//step 5 : Add to rear of queue all the neighbours of N,//that are in ready state and change their status to//wait state.
tmp = adj[N];  //for status updation.while(tmp!=NULL){
v = tmp->vertex;
q_insert(v); //insert N's neighbour who are in ready state.
status[v]=wait; //and make their status to wait state.
}
tmp=tmp->next;
}
}
}

void main(){
clrscr();
createGraph();
cout<<"\n===BFS traversal is as under===\n";
BFS_traversal();
getch();
}```
Share:

Didn't find what you were looking for? Find more on Program of Breadth First Search Traversal ( BFS ) Or get search suggestion and latest updates.

 Easy Tutor author of Program of Breadth First Search Traversal ( BFS ) is from United States. Easy Tutor says Hello Friends,I am Free Lance Tutor, who helped student in completing their homework. I have 4 Years of hands on experience on helping student in completing their homework. I also guide them in doing their final year projects.I have share many programs on this website for everyone to use freely, if you need further assistance, than please contact me on easytutor.2ya [at the rate] gmail [dot] comI have special discount scheme for providing tutor services. I am providing tutor service to students from various contries, currently most of my students are from United States, India, Australia, Pakistan, Germany, UK and Canada. I am also here to expand my technical network to receive more opportunity in my career, make friends to help them in resolving their technical problem, learn and share my knowledge, If you like to be my friend, Please send me friend request.Thanks,Happy Programming :) View All Articles