DFS algorithm implementing with c program

DFS  or  depth first search algorithm technique is used mainly for graphs . It is recursive algorithm.

Followed in all Btech or BE  colleges and books in India as well as all over the world

#include<stdio.h>

#include<stdlib.h>

#define white 0

#define gray 1

#define black 2

#define nil -1

struct node


int data;

struct node *next;

;

struct attribute


int color,d,p,f;

;

void dfs(struct node **,int,struct attribute *,int *);

void dfs_visit(struct node **,int,struct attribute *,int *);

int main()


FILE *fp;

int **a,n,i,j,time;

struct node **arr,*head,*x,*temp;

struct attribute *na;

fp=fopen(“dfs.txt”,”r”);

if(fp==NULL)


printf(“Unable to open the file”);

exit(0);

fscanf(fp,”%d”,&n);

a=(int**)malloc(sizeof(int*)*(n+1));

for(i=1;i<=n;i++)

a[i]=(int*)malloc(sizeof(int)*(n+1));

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

fscanf(fp,”%d”,&a[i][j]);

//print adjacency matrix

printf(“Adjacency Matrix:\n”);

for(i=1;i<=n;i++)


for(j=1;j<=n;j++)

printf(“%d “,a[i][j]);

printf(“\n”);


arr=(struct node**)malloc(sizeof(struct node *)*(n+1));

for(i=1;i<=n;i++)


head=NULL;

for(j=1;j<=n;j++)


if(a[i][j]==1)


x=(struct node*)malloc(sizeof(struct node));

x->data=j;

x->next=NULL;

if (head==NULL)

head=x;

else


temp=head;

while(temp->next!=NULL)

temp=temp->next;

temp->next=x;




arr[i]=head;

//display adjacency list

printf(“\nAdjacency Lists:\n”);

for(i=1;i<=n;i++)


printf(“\tNODE %d: “,i);

head=arr[i];

while(head!=NULL)


printf(“%d “,head->data);

head=head->next;


printf(“\n”);

na=(struct attribute *)malloc(sizeof(struct attribute)*(n+1));

dfs(arr,n,na,&time);

printf(“\n NODE   COLOR   DISTANCE   PARENT   FINISHING TIME\n”);

for(i=1;i<=n;i++)


printf(“%d  %d  %d  %d  %d”,i,na[i].color,na[i].d,na[i].p,na[i].f);

printf(“\n”);


return 0;

void dfs(struct node **arr,int n,struct attribute *na,int *time)

struct node *h;

int v,u,i,d,z;

for(u=1;u<=n;u++)


na[u].color=white;

na[u].p=nil;


*time=0;

for(u=1;u<=n;u++)


if(na[u].color==white)


dfs_visit(arr,u,na,time);



/*printf(“NODE   COLOR   DISTANCE   PARENT   FINISHING TIME”);

for(i=1;i<=n;i++)


printf(“%d\t%d\t%d\t%d\t%d”,i,na[i].color,na[i].d,na[i].p,na[i].f);

printf(“\n”);

*/

void dfs_visit(struct node **arr,int u,struct attribute *na,int *time)


int v;

struct node *h;

*time=*time+1;

na[u].d=*time;

na[u].color=gray;

h=arr[u];

while(h!=NULL)


v=h->data;

if(na[v].color==white)


na[v].p=u;

dfs_visit(arr,v,na,time);


h=h->next;


na[u].color=black;

*time=*time+1;

na[u].f=*time;

DFS algorithm implementing with c program