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