PROGRAM TO IMPLEMENT DEPTH FIRST SEARCH


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<alloc.h>
#define max 100
void dfs(int n);
void dfs_visit(int u);
int color[max];
int d[max];
int f[max];
int time1;
typedef struct vert* ver;
struct vert
{
int ident;
ver next;
}cor;
ver adj_list[max];
void main()
{
int n,i,j,k,s,u;
ver temp,prev;
clrscr();
printf("Enter no. of nodes");
scanf("%d",&n);
for(i=0;i<=n;i++)
adj_list[i]='\0' ;
for(i=1;i<=n;i++)
{
prev=NULL;
printf("enter no. of vertex connected to %d",i);
scanf("%d",&j);
for(k=0;k<j;k++)
{
temp=(ver)malloc(sizeof(cor));
temp->next=NULL;
printf("Enter vertex no. connected to vertex %d",i);
scanf("%d",&temp->ident);
if(prev==NULL)
adj_list[i]=temp;
else
prev->next=temp;
prev=temp;
}
}
dfs(n);

for(i=1;i<=n;i++)
{
printf("\n starting/ending time of vertex %d is %d/%d",i,d[i],f[i]);
}
getch();
}
void dfs(int n)
{
int i;
for(i=1;i<=n;i++)
color[i]=0;
time1=0;
for(i=1;i<=n;i++)
{
if(color[i]==0)
dfs_visit(i);
}
}

void dfs_vist(int u)
{

ver temp;
color[u]=1;
time1++;
d[u]=time1;
temp=adj_list[u];
while(temp!=NULL)
    {
    if(color[temp->ident]==0)
    dfs_vist(temp->ident);

temp=temp->next;
}
color[u]=2;
f[u]=++time1;
}

Comments

Popular posts from this blog

REFLECTION OF A TRIANGLE (COMPUTER GRAPHICS)