/*
DFS TRAVERSAL
ROLL NO:- 09BCE006
*/
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
void create();
void dfs();
struct node
{
int data,status;
struct node *next;
struct link *adj;
}*start,*p,*q;
struct link
{
struct node *next;
struct link *adj;
}*l,*k;
void main()
{
clrscr();
create();
dfs();
}
void create()
{
int dat,flag=0;
start=NULL;
cout<<"Enter the nodes in the graph (0 to end):\n\n";
while(1)
{
cin>>dat;
if(dat==0)
break;
p=new node;
p->data=dat;
p->status=0;
p->next=NULL;
p->adj=NULL;
if(flag==0)
{
start=p;
q=p;
flag++;
}
else
{
q->next=p;
q=p;
}
}
p=start;
while(p!=NULL)
{
cout<<"\nEnter the links of "<<p->data<<"(0 to end)\n";
flag=0;
while(1)
{
cin>>dat;
if(dat==0)
break;
k=new link;
k->adj=NULL;
if(flag==0)
{
p->adj=k;
l=k;
flag++;
}
else
{
l->adj=k;
l=k;
}
q=start;
while(q!=NULL)
{
if(q->data==dat)
k->next=q;
q=q->next;
}
}
p=p->next;
}
return;
}
void dfs()
{
int stack[25],top=1;
cout<<"\nDFS result is\n";
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
stack[0]=0;
stack[top]=p->data;
p->status=1;
while(1)
{
if(stack[top]==0)
{
break;
}
p=start;
while(p!=NULL)
{
if(p->data==stack[top])
{
break;
}
p=p->next;
}
cout<<stack[top]<<" ";
top--;
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
top++;
stack[top]=q->data;
q->status=1;
}
k=k->adj;
}
}
getch();
return;
}
Posts
