How to do it...

Follow these steps for the depth-first traversal of a graph:

1. Push the first vertex of the graph into the stack. You can choose any vertex of the graph as the starting vertex.
2. Then, repeat the following steps 3 to 7 until the stack is empty.
3. Pop the vertex from the stack and call it by any name, say, v.
4. Mark the popped vertex as visited. This marking is done so that this vertex should not be traversed again.
5. Display the marked vertex.
6. Find out the adjacency vertices of the v vertex, and then perform step 7 on each of them.
7. If any of the adjacency vertices of v are not marked, mark them as visited and push them on to the stack.
8. Exit.

The program for the depth-first traversal of a graph is as follows:

//depthfirsttrav.c


#include <stdlib.h>
#include <stdio.h>
#define max 20

enum Setmarked {Y,N};
struct node {
  char nme;
  struct node * vrt;
  struct node * edg;
  enum Setmarked marked;
};

struct node * stack[max];
int top = -1;
void push(struct node * h);
struct node * pop();

int main() {
  int numb, i, j, noe;
  char v1, v2;
  struct node * startList, * newNode, * temp1, * temp2, * temp3;
  printf("How many vertices are there ?");
  scanf("%d", & numb);
  startList = NULL;
  printf("Enter all vertices names\n");
  for (i = 1; i <= numb; i++) {
    if (startList == NULL) {
      newNode = malloc(sizeof(struct node));
      scanf(" %c", & newNode - > nme);
      /* There is a white space before %c */
      startList = newNode;
      temp1 = newNode;
      newNode - > vrt = NULL;
      newNode - > edg = NULL;
      newNode - > marked = N;
    } else {
      newNode = malloc(sizeof(struct node));
      scanf(" %c", & newNode - > nme);
      /* There is a white space before %c */
      newNode - > vrt = NULL;
      newNode - > edg = NULL;
      newNode - > marked = N;
      temp1 - > vrt = newNode;
      temp1 = newNode;
    }
  }
  printf("Enter the edges between vertices. Enter v1 v2, if there is an edge\n");
  printf("between v1 and v2. Enter 0 0 if over\n");
  noe = numb * (numb - 1);
  for (j = 1; j <= noe; j++) {
    scanf(" %c %c", & v1, & v2);
    /* There is a white space before %c */
    if (v1 == '0' && v2 == '0') break;
    temp1 = startList;
    while (temp1 != NULL && temp1 - > nme != v1)
      temp1 = temp1 - > vrt;
    if (temp1 == NULL) {
      printf("Sorry no vertex exist by this name\n");
      break;
    }
    temp2 = temp1;
    while (temp2 - > edg != NULL) temp2 = temp2 - > edg;
    newNode = malloc(sizeof(struct node));
    newNode - > nme = v2;
    temp2 - > edg = newNode;
    newNode - > edg = NULL;
    newNode - > vrt = NULL;
  }
  printf("\nAdjacency List representation of Graph is\n");
  temp1 = startList;
  while (temp1 != NULL) {
    printf("%c\t", temp1 - > nme);
    temp2 = temp1 - > edg;
    while (temp2 != NULL) {
      printf("%c\t", temp2 - > nme);
      temp2 = temp2 - > edg;
    }
    printf("\n");
    temp1 = temp1 - > vrt;
  }
  printf("\nDepth First traversal of the graph is \n");
  temp1 = startList;
  if (temp1 == NULL)
    printf("Sorry no vertices in the graph\n");
  else
    push(temp1);
  while (top >= 0) {
    temp3 = pop();
    temp1 = startList;
    while (temp1 - > nme != temp3 - > nme) temp1 = temp1 - > vrt;
    temp3 = temp1;
    if (temp3 - > marked == N) {
      printf("%c\t", temp3 - > nme);
      temp3 - > marked = Y;
      temp2 = temp3 - > edg;
      while (temp2 != NULL) {
        push(temp2);
        temp2 = temp2 - > edg;
      }
    }
  }
  return 0;
}

void push(struct node * h) {
  top++;
  stack[top] = h;
}

struct node * pop() {
  return (stack[top--]);
}

Now, let's go behind the scenes to understand the code better.