Data Structure Program to Implement DFS

Implement DFS for an undirected or digraph.
/* Depth First Search Traversal - DFS - Directed Graph - Recursive */

#include
#include

#define MAXVERTS 10 /* maximum vertices in the
graph <= 10 */

void main(void)
{
void dfs(int [][MAXVERTS], int [], int); /* prototype
declaration for */
/* depth first search traversal function */
int adj_mat[MAXVERTS][MAXVERTS]; /* array to hold
the adjecancy matrix */
int visited[MAXVERTS]; /* array to hold if node is
already visited */
int n; /* stores actual number of vertices present in
graph */
int m; /* stores total no of edges in the directed
graph */
int start; /* stores the vertex at which the DFS begins */
int i,j,k; /* loop variables */
input : /* label name for transfer of control through
goto */
clrscr();
printf("DFS Traversal - Directed Graphs - Recursive\n");
printf("--- --------- - -------- ------ - ---------\n\n");
printf("Enter number of vertices in the directed graph [0
to exit] - ");
flushall();
scanf("%d", &n);
if (n < 0 || n > MAXVERTS) /* check for valid input
*/
{
printf("Maximum vertices in the directed graph =
%d\n",MAXVERTS);
printf("Error - input value is out of range...[0 to 10]");
getch();
goto input;
}
if (n == 0)
{
goto end;
}
for (i=0; i {
visited[i] = 0; /* initialize visited array to zeroes or false
*/
for (j=0; j {
adj_mat[i][j] = 0; /* initialize adjecancy matrix */
}
}
printf("Enter total number of edges in the directed
graph - ");
flushall();
scanf("%d", &m);
for (k=1; k<=m; k++)
{ /* This loop asks details of the edges in the graph */
printf("\nEdge no = %2d is -\nFrom vertex number = ",
k);
flushall();
scanf("%d",&i);
printf("upto vertex number = ");
flushall();
scanf("%d",&j);
if (i<1 || i>n || j<1 || j>n)
{
printf("Error - check details of this edge\n");
printf("wrong vertex numbers...");
getch();
goto input;
}
adj_mat[i-1][j-1]=1; /* sets the proper element in the */
/* adjecancy boolean matrix to
a value 1 */
}
printf("\n\nEnter vertex no at which to start DFS [%d to
%d] - ", 1, n);
flushall();
scanf("%d",&start);
if (start < 1 || start>n)
{
printf("Error - input value is out of range...[0 to 10]");
getch();
goto input;
}
clrscr();
printf("Adjecancy Matrix - \n", n);
printf("--------- ------ - \n\n\n");
for (i=0; i {
for (j=0; j {
printf(" %d ",adj_mat[i][j]); /* displays the contents of
the */
} /* adjencancy boolean matrix */
printf("\n\n");
}
printf("\n\n\nDFS Traversal starting at vertex no %d
-\n",start);
printf("--- --------- -------- -- ------ -- - -\n\n\n");
dfs(adj_mat,visited,(start-1)); /* invoke the function for
performing */
/* DFS traversal starting at a particular vertex */
printf("\n\n");
getch();
goto input;
end :
printf("\n\n\bEnd of Program");
getch();
}

/* Recursive Function definition for DFS traversal of
graph starting at */
/* a particular vertex */
void dfs(int adj_mat[][MAXVERTS], int visited[], int
start)
{
int i; /* local loop variable */
printf("%d ",(start+1)); /* display the current vertex as
visited */
visited[start] = 1; /* set the flag for visited to 1 */
for (i=0; iother vertices */
{
if (adj_mat[start][i] && visited[i] == 0) /* check for
adjecancy and */
{ /* not visited status of the ith vertex */
dfs(adj_mat, visited, i); /* recursive call to the DFS
function */
}
}
}