Wednesday, 5 March 2014

depth 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],s[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;
s[i]=0;
             }
cout<<"\nEnter the key to be found::";
cin>>key;
cout<<"\nDFS Path is:\t";
search(0,key);
cout<<"\n";
system("pause");
}

void search(int k,int key)
{
if((b[k]==0)&&(s[k]==0))
  {
  if(k==key)
{
cout<<k<<"\t";
  cout<<"\nElement found\n";
  return;
  }
  else
  cout<<k<<"\t";

b[k]=1;
s[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 found!!\n";
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);
if(a[z][y]==1)
return(y);
else
             {
q=getnode();
q->info =y;
if(front == NULL)
front =q;
else
            rear->next=q;
rear=q;
for(i=z+1;i<n;i++)
{
if((a[z][i]==1)&&(s[i]==0))
{
return z;
}
}
for(i=0;i<n;i++)
{
if((a[z][i]==1)&&(b[i]==1))
return i;
}
return z;
        }
}

No comments:

Post a Comment