Wednesday, 5 March 2014

breadth first search

#include<iostream>
#include<stdio.h>
using namespace std;
void search(int,int);
int i,j,n,y,x;
int a[10][10],b[10];
struct queuenode
{
int info;
struct queuenode *next;
};
typedef struct queuenode *QUEUE;
QUEUE front,rear,q;
QUEUE getnode()
{
QUEUE p;
p=(QUEUE)malloc(sizeof(struct queuenode));
return p;
}
void insert(QUEUE q,int x);
int qdel(QUEUE q,int x);
void main()
{
int key;
front=rear=NULL;
printf("\nEnter the number of vertices:\n");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
           {
for(j=0;j<n;j++)
                      {
cin>>a[i][j];
              }
    cout<<"\n";
        }
cout<<"\nThe adjacency matrix is:\n";
for(i=0;i<n;i++)
           {
for(j=0;j<n;j++)
                      {
cout<<a[i][j]<<"\t";
                        }
cout<<"\n";
        }
for(i=0;i<n;i++)
           {
b[i] = 0;
           }
cout<<"\nEnter the key to be found::\n";
cin>>key;
cout<<"\n\nBFS Path is:\t";
search(0,key);
           cout<<"\n";
system("pause");
}

void search(int k, int key)
{
if(b[k]==0)
{
if(k==key)
{
cout<<k<<"\t";
cout<<"\nElement found!\n";
return;
}
else
{
cout<<k<<"\t";
           }
b[k]=1;
for(i=0;i<n;i++)
                       {
if(a[k][i]==1)
                                 {
if(b[i]==0)
                      {
insert(q,i);
                                             }
}
        }
   }
if(front==NULL)
{
cout<<"\nElement not present!";
return;
}
else
{
x=qdel(q,k);
      search(x,key);
}
}
void insert(QUEUE q,int x)
{
QUEUE p;
p=getnode();
p->info=x;
if(front==NULL)
front = p;
else
rear->next=p;
rear=p;
}
int qdel(QUEUE q,int z)
{
q=front;
y=q->info;
if(front==rear)
front=rear=NULL;
else
front=front->next;
free(q);
return y;

}

No comments:

Post a Comment