Breadth First Search


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

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

About these ads

12 thoughts on “Breadth First Search”

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

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

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

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s