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

---

Possibly related posts: (automatically generated)

• Lovebug Lovebug – Jonas Brothers Titled you for the first time …