Depth first search (DFS) with C Language code

Depth first search (DFS) with C Language code

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes
 

Pseudocode

Input: A graph G and a vertex v of G

Output: All vertices reachable from v labeled as discovered

A recursive implementation of DFS:

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

A non-recursive implementation of DFS:

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v ← S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

C Language Code

/* 

  Program dfs.cpp is depth first search traversal.

  Input is adjacency matrix and its uses stack operation for non-

  recursive implementation 

*/

#include <stdio.h>

#include <stdlib.h>

# include<conio.h>

#define MAXSIZE 20

#define TRUE 1

#define FALSE 0

struct stackType

{

  int top;

  int items[MAXSIZE];

} stack;

int pop(struct stackType *);

void push(struct stackType *, int);

int empty(struct stackType *);

void adjMatrix(int[MAXSIZE][MAXSIZE], int);

void DFS(int[MAXSIZE][MAXSIZE],int,int);

void main()

{

  int aMat[MAXSIZE][MAXSIZE], noVertices, startVertex;

  clrscr();

  stack.top = -1;     /* Initialize stack to empty */

  printf("Enter number of vertices in graph : ");

    scanf("%d", &noVertices);

  printf("\n\n");

  adjMatrix(aMat, noVertices);

  printf("Enter start vertex [1 to %d] : \n", noVertices);

    scanf("%d", &startVertex);

  DFS(aMat, startVertex, noVertices);

  getch();

}

/* Input function */

void adjMatrix(int aMat[MAXSIZE][MAXSIZE], int no)

{

  int i, j;

  printf("Input adjacency matrix of order %dx%d\n", no, no);

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

  {

    printf("Row %d : ", i);

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

      scanf("%d", &aMat[i][j]);

  }

}

void DFS(int aMat[MAXSIZE][MAXSIZE], int startVertex, int no)

{

  int i,j, visited[MAXSIZE], node;

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

    visited[i]=0;

  node = startVertex;

  visited[node] = 1;

  printf("DFS traversal sequence (start vertex = %d)\n", startVertex);

  while (1)

  {

    printf(" %d ", node);

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

    {

      if ((aMat[node][j]==1) && (visited[j]==0))

      {

push(&stack, j);

visited[j] = 1;

      }

    }

    if (empty(&stack))

    {

      printf("\n");

      return;

    }

    else

      node = pop(&stack);

  }

}

/* function push the integer element into stack s */

void push(struct stackType *stack, int no)

{

  if (stack->top == MAXSIZE-1)

  {

    printf("%stack", "stack overflow");

    return;

  }

  else

    stack->items[++(stack->top)] = no;

  return;

}

/* function pop the integer element from stack */

int pop(struct stackType *stack)

{

  if (empty(stack))

  {

    printf("\n%s", "stack underflow");

    return;

  }

  return(stack->items[stack->top--]);

}

int empty(struct stackType *stack)

{

  if (stack->top == -1)

    return (TRUE);

  else

    return (FALSE);

}