PROGRAM TO PERFORM DFS | Data Structures Tutorial pdf

/*PROGRAM TO PERFORM DFS*/

#include<stdio.h>
#define max 20
#define t 1
#define f 0
struct edge
{
int leaf;
struct edge *link;
};
struct vertex
{
int visit;
int vertex_no;
char info;
int path_length;
struct edge *edge_ptr;
};
void table(int , int matrix [max][max], struct vertex vert[max]);
struct edge *insert_vertex (int , struct edge *);
void dfs ( int , int *dist, struct vertex vert [max]);
void input(int, int a [max][max]);
void output(int, int a [max][max]);
struct edge * insert_vertex (int vertex_no, struct edge *first)
{
struct edge *new1, *current;
new1 = (struct edge *) malloc(sizeof(struct edge));
new1->leaf = vertex_no;
new1->link = NULL;
if (!first)
return (new1);
for (current = first; current->link; current = current->link);
current->link = new1;
return (first);
}

/* Function to initialize entries */
void table(int vertex_num,int matrix[max][max],struct vertex vert[max])
{
int i, j;
for (i = 0; i < vertex_num; i++)
{
vert [i].visit = f;
vert [i].vertex_no = i+1;
vert [i].info = 'A'+ i;
vert [i].path_length = 0;
vert [i].edge_ptr = NULL;
}
for (i =0; i < vertex_num ; i++)
for (j =0; j < vertex_num ; j++)
if (matrix [i][j] > 0)
vert [i].edge_ptr = insert_vertex (j, vert [i].edge_ptr);
}

/* Function to calculate path length */
void dfs (int index,int *dist,struct vertex vert [max])
{
struct edge *link;
vert [index].visit = t;
vert [index].path_length = *dist;
*dist += 1;
for ( link = vert [index].edge_ptr; link; link = link->link)
if (vert [link->leaf].visit == f)
dfs (link->leaf, dist, vert);
}

/* Function to read adjacency matrix */
void input(int num, int a [max][max])
{
int i, j;
printf("\n\n Enter adjacency matrix \n");
for (i =0; i < num; i++)
{
for (j=0; j < num; j ++)
{
scanf("%d", &a [i][j]);
}
printf("\n");
}
}

/* Function to display result */
void output(int num, int a [max][max])
{
int i, j;
printf("\n\n\t Adjacency matrix \n\n\t");
for (i = 0; i < num; i++)
{
for (j = 0; j < num; j ++)
{
printf(" %d", a [i][j]);
}
printf("\n\t");
}
}

/* Main Function */
void main()
{
int i;
int num, index, dist;
int a [max][max];
struct vertex vert [max];
struct edge *list;
clrscr();
printf("\n\n Enter number of vertices: ");
scanf("%d", &num);
input(num, a);
output(num, a);
table(num, a, vert);
printf("\n\n Enter number of starting vertex:");
scanf("%d", &index);
dist = 0;
dfs (index, &dist, vert);
printf("\n\n Shortest path from %c to other vert:", vert[index].info);
for (i = 0; i < num; i++)
{
printf("\n %c %d ", vert[i].info, vert[i].path_length);
for (list= vert[i].edge_ptr; list; list = list->link)
{
printf(" ");
putchar(list->leaf+'A');
}
}
getch();
}