Sunday, December 12, 2010

Depth First Search Algorithm

//program to perform Depth First Search Algorithm
#include
#include

class dfs
{
char vertex[10],visit[10],v;
int gptr[10][10],stack[10],top;
int n,k,v1,u;
public:
dfs()
{
top=0;
k=0;v1=0;
}
void input();
void dfs_am(int);
void push(int);
int pop();
int search(int);
void insert(int);
void disp();
};

void dfs::input()
{
cout<<"Enter the no of vertices:";
cin>>n;
if(n==0)
cout<<"\nThe tree is empty";
else if(n==1)
cout<<"There is only one vertex";
else
{
cout<<"Enter the vertices:";
for( int i=1;i<=n;i++)
cin>>vertex[i];
cout<<"Enter the adjacency matrix:\n";
for(i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>gptr[i][j];
cout<<"\nEnter the vertex from which the traversal begin:";
cin>>v;

//find index of the source vertex
for(i=1;i<=n;i++)
{
if(vertex[i]==v)
v1=i;
if(v1!=0)
break;
}
cout<<"Traversal from "< dfs_am(v1);
}
}


void dfs::dfs_am(int v)
{
u=v;
push(u);
while(top!=0)
{
u=pop();
if(search(u)==0)
{
insert(u);
for(int i=1;i<=n;i++)
if(gptr[u][i]==1)
push(i);
}
}
}


//function to push a vertex into the stack
void dfs::push(int u1)
{
top=top+1;
stack[top]=u1;
}

//function to pop a vertex from the stack
int dfs::pop()
{
int item;
item=stack[top];
top=top-1;
return item;
}


//functon to unsert a vertex into the array visit
void dfs::insert(int u1)
{
k=k+1;
visit[k]=vertex[u1];
}

//functon to search a vertex already exist
int dfs::search(int u)
{
int flag=0;
if(k>=1)
{
for(int i=1;i<=k;i++)
{
if(visit[i]==vertex[u])
flag=1;
}
}
return flag;
}

void dfs::disp()
{
if(n==1)
return;
for(int i=1;i<=k;i++)
cout<<"\t"< }
void main()
{
dfs s;
clrscr();
cout<<”DEPTH FIRST SEARCH\n-----------------------------\n”;
s.input();
s.disp();
getch();
}




OUTPUT


Enter the no of vertices:4
Enter the vertices:a b c d
Enter the adjacency matrix:
0 1 1 0
1 0 0 0
1 0 0 1
0 0 1 0

Enter the vertex from which the traversal begin:a
Traversal from a is a c d b

No comments:

Post a Comment