Thursday 29 November 2012

Breadth First Search(BFS) graph traversal


/*Breadth First Search(BFS) Traversal
compiler- Turbo c++     author- Mangilal Sharma
--------------------------------------------------------*/
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>

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

class bfs
{
 public:
 void create();  // For creating a graph
 bfs();          // For Breadth First Search(BFS) Traversal.
 struct node *start,*p,*q;
 struct link *l,*k;
};

void bfs::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;
}

// Breadth First Search(BFS) Traversal.
void bfs::bfs()
{
 char ch='y';
 while(ch=='y'||ch=='Y')
 {
  clrscr();
  create();
  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++;
  }
  cout<<"\n\nEnter Y/y For again enter:";
  cin>>ch;
 }return;
}
/*=========================16Nov.,2010=============================*/

No comments:

Post a Comment

You are welcome, your comment helps me to make this blog more better.