/**********************************************************************

-> This Program is to implement Breadth First search.

-> Data Structers:
-> This program works in microsoft vc++ 6.0 environment.

************************************************************************/

#include<iostream.h>

class Queue
{
private:
int data;
Queue*next;
public:
void Enque(int);
int Deque();
void Queue::Enque(int data)
{
Queue *temp;
temp=new Queue;
temp->data=data;
temp->next=NULL;
else
tail->next=temp;
tail=temp;
}
int Queue::Deque()
{
Queue* temp;
return temp->data;
}

int visit[100];
int bfs_span_tree[100][100];

class graph
{
private:
int a;
graph*next;
public:
void bfs();
graph* create(graph*);
void ftraverse(graph*);
};

{
int a;
graph*last;
graph*temp;
cout<<“Enter  adjecent node ,-1 to stop:\n”;
cin>>a;
while(a!=-1)
{
temp=new graph;
temp->a=a;
temp->next=NULL;
else
last->next=temp;
last=temp;
cout<<“Enter  adjecent node ,-1 to stop:\n”;
cin>>a;
}
}

void graph::ftraverse(graph*h)
{
while(h!=NULL)
{
cout<<h->a<<“->”;
h=h->next;
}
cout<<“NULL\n”;
}

void graph::bfs()
{
cout<<“**********************************************************\n”;
cout<<“This program is to implement bfs for an unweighted graph \n”;
cout<<“**********************************************************\n”;

graph *ptr[100];
int n;
cout<<“Enter the no. of nodes in the grph:”;
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<“Enter the adjacent nodes to node no. “<<i<<endl;
cout<<“***************************************\n”;
ptr[i]=create(ptr[i]);
}
cout<<“\n\nThe Entered Graph is ::\n”;
for(i=1;i<=n;i++)
{
cout<<“< “<<i<<” > ::”;
ftraverse(ptr[i]);
}

int x;
cout<<“\nEnter the start node <1,…”<<n<<“>:”;
cin>>x;
cout<<“\n\nThe Breadth first search traversal is:\n”;
Queue object;

//Mark all the nodes as not viseted
for(i=1;i<=n;i++)
{
visit[i]=0;
}
for(i=1;i<=n;i++)
for(int j=1;j<=n;j++)
bfs_span_tree[i][j]=0;

//Enque the start node
object.Enque(x);

int p;
{
//Deque a node
p=object.Deque();
int x=p;
//If it is not visited yet

while(ptr[p]!=NULL)
{
if(visit[ptr[p]->a]!=1)
{
cout<<“node “<<ptr[p]->a<<” is visited\n”;
//Mark the node as visited
visit[ptr[p]->a]=1;
bfs_span_tree[ptr[p]->a][x]=1;
}
object.Enque(ptr[p]->a);
ptr[p]=ptr[p]->next;
}

}

cout<<“\n\nThe required bfs spanning tree is ::\n\n”;
for(i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<bfs_span_tree[i][j]<<‘ ‘;
cout<<endl;
}

cout<<endl;
}
int main()
{
graph obj;
obj.bfs();
return 0;
}

## 12 thoughts on “Breadth First Search”

1. faizkarim says:

Implement in C++ Bredth First Search and print the path length (no. of edges) between nodes i and j.
The graph is undirected and unweighted and the adjacency matrix is given as input.
Eg:
Input:
0 1 0
1 0 1
0 1 0
1 3
Output:
2

give me sourse code of this question. please

2. puneet kharbanda says:

yaar its nt working gv me the wrkng one

fine code but please give detail about code what is going on in code… thanx

4. KIRTIRAJ says:

1. Write a program to create a tree of depth=6 & branching factor=2. The program should display the tree on the screen. Each node in the tree must be named. It should also provide the facility to select a specific node as a goal node (by means of mouse click) in the tree and then to display path to the goal node (by means of highlighting the path) using bfs..plz gv me dis problem of dis code

5. aj says:

Salams and hi there everyone.

Initially i got some 102 errors but the errors were just due to the double and single quotes. When you copy from here these are the only things you have to change and rewrite. After doing this there are no errors left. Hope this solves the problem for puneet kharbanda and many others.

102 error!!!

6. I think you should include some more details regarding interview.

7. ankur says:

its a perfect program,with very minor errors

8. this really worked bro, though I had to make just a little bit of changes!! and this is the simplest way one can understand bfs in c++… I always wondered about how to implement one bfs in programming though I knew all the procedures and all….

Thank you once again….

9. doomdon says:

The above program gives a seg fault in the following scenario:
I entered a total of 5 nodes
for 1st node, I entered adjacent nodes: 1,2,3,4,5

for 1st node, I entered adjacent nodes: 6,7,8,9,10
for 2nd node, I entered adjacent nodes: 11,12,13,14,15
for 3rd node, I entered adjacent nodes: 16,17,18,19,20
for 4th node, I entered adjacent nodes: 21,22,23,24,25
for 5th node, I entered adjacent nodes: 26,27,28,29,30

Then, I entered the start node as 1
& the output was:

The Breadth first search traversal is:
node 1 is visited
node 2 is visited
node 3 is visited
node 4 is visited
node 5 is visited
node 6 is visited
node 7 is visited
node 8 is visited
node 9 is visited
node 10 is visited
node 11 is visited
node 12 is visited
node 13 is visited
node 14 is visited
node 15 is visited
node 16 is visited
node 17 is visited
node 18 is visited
node 19 is visited
node 20 is visited
node 21 is visited
node 22 is visited
node 23 is visited
node 24 is visited
node 25 is visited
node 0 is visited
Segmentation fault

10. doomdon says:

The above program gives a seg fault in the following scenario:
Ignore the above post, there was a mistake in it.
I entered a total of 5 nodes
for 1st node, I entered adjacent nodes: 1,2,3,4,5
for 2nd node, I entered adjacent nodes: 6,7,8,9,10
for 3rd node, I entered adjacent nodes: 11,12,13,14,15
for 4th node, I entered adjacent nodes: 16,17,18,19,20
for 5th node, I entered adjacent nodes: 21,22,23,24,25

Then, I entered the start node as 1
& the output was:

The Breadth first search traversal is:
node 1 is visited
node 2 is visited
node 3 is visited
node 4 is visited
node 5 is visited
node 6 is visited
node 7 is visited
node 8 is visited
node 9 is visited
node 10 is visited
node 11 is visited
node 12 is visited
node 13 is visited
node 14 is visited
node 15 is visited
node 16 is visited
node 17 is visited
node 18 is visited
node 19 is visited
node 20 is visited
node 21 is visited
node 22 is visited
node 23 is visited
node 24 is visited
node 25 is visited
node 0 is visited
Segmentation fault