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

-> This Program is to implement Breadth First search.

-> Data Structers:

Graph:Adjacency List

Queue:Linked List

-> 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();

}*head,*tail;

void Queue::Enque(int data)

{

Queue *temp;

temp=new Queue;

temp->data=data;

temp->next=NULL;

if(head==NULL)

head=temp;

else

tail->next=temp;

tail=temp;

}

int Queue::Deque()

{

Queue* temp;

temp=head;

head=head->next;

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*);

};

graph* graph::create(graph*head)

{

int a;

graph*last;

head=last=NULL;

graph*temp;

cout<<“Enter adjecent node ,-1 to stop:\n”;

cin>>a;

while(a!=-1)

{

temp=new graph;

temp->a=a;

temp->next=NULL;

if(head==NULL)

head=temp;

else

last->next=temp;

last=temp;

cout<<“Enter adjecent node ,-1 to stop:\n”;

cin>>a;

}

return head;

}

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;

while(head!=NULL&&tail!=NULL)

{

//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;

}

//Enque all its adjacent nodes

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;

}

people are stranger

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

yaar its nt working gv me the wrkng one

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

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

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!!!

I think you should include some more details regarding interview.

its a perfect program,with very minor errors

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….

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

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