Depth-First Graph Traversal using Stack — a C Implementation

There’re two common ways of visiting all nodes of a graph, depth-first search and breadth-first search. These two graph traversal approaches relate to two popular data structures, stack and queue respectively. (One can also do it in a recursive manner. It’s more intuitive but less efficient.)

This post covers depth-first search with a stack data structure. The algorithm expressed in pseudo code is as below,

DFS (Graph, root):
   create a stack S
   push root node to S
   while S is not empty:
       pop an itme v from S
       mark the item v as visited
       for each node w that is directed from v:
           if w is not visited:
               push w to S

The first step of the implementation is to implement a stack. The stack implemented below has the basic functions like push, pop, ifEmpty, etc.

1. Stack Implementation

The header file stack.h, defines the data structures used in Stack and Graph.

#include <stdio.h>
#include <stdlib.h>
typedef struct Point {
   int h;
   int w;
} Point;
typedef struct GraphNode {
   struct Point pvalue;
   struct GraphNode* left;
   struct GraphNode* right;
} GraphNode;
typedef struct StackElement {
   struct GraphNode value;
   struct StackElement *up;
   struct StackElement *down;
} StackElement;
typedef struct Stack {
   struct StackElement* topP;
   struct StackElement* bottomP;
} Stack;
void initStack(struct Stack *s);
void push(struct Stack *s, struct GraphNode _value);
void pop(struct Stack *s);
struct GraphNode top(struct Stack *s);
int ifEmpty(struct Stack *s);

The actual implementation stack.c

/**
a C stack implementation using linked list
*/
#include "stack.h"
/*initialize the stack*/
void initStack(struct Stack *s) {
   s->topP = NULL;
   s->bottomP = NULL;
}
/*add an element to the top of the stack*/
void push(struct Stack *s, struct GraphNode _value) {
   //allocate a new StackElement for _value
   StackElement *newElement;
   newElement = (StackElement*) malloc(sizeof(StackElement));
   newElement->value = _value;
   newElement->up = NULL;
   newElement->down = NULL;
   if (s->topP == NULL) {
        //first element
       s->topP = newElement;
        s->bottomP = newElement;
   } else {
        //push it to the top
        newElement->down = s->topP;
        s->topP = newElement;
   }
}
/*delete the top element from the stack*/
void pop(struct Stack *s) {
   StackElement *element;
   if (s->topP == NULL) {
        //empty stack
        return;
   } else {
        element = s->topP;
        s->topP = element->down;
        if (s->topP != NULL)
             s->topP->up = NULL;
        free(element);
   }
}
/*get the top value of the stack, but don't delete it*/
struct GraphNode top(struct Stack *s) {
   return s->topP->value;
}
/*check if the stack is empty*/
int ifEmpty(struct Stack *s) {
   return (s->topP == NULL ? 1:0);
}

Note that the top() function above returns the top element of the stack and the pop() function deletes the top element from the stack. Some stack implementations has the pop() function does both return and delete. But I personally think separating them is more convenient as sometimes you just want to take a look at the stack but not delete anything from it.

The Stack above will take input element of GraphNode type, but you’re free to modify it to fit your needs.

2. The Depth-First Graph Traversal

For simplicity, an example of visiting all nodes of a binary tree is given below. The tree structure is included in the comment of the source code file dfs.c,

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
/* a simple graph (binary tree)
         (0,    3)   <– root node
          /     \
      (1, 2)    (1,4)
       /  \     /   \
   (2,1) (2,2) (2,3) (2,5)
*/
typedef struct Graph {
   struct GraphNode* root;
} Graph;
struct GraphNode initNode(int _h, int _w) {
   struct GraphNode node;
   node.pvalue.h = _h;
   node.pvalue.w = _w;
   node.left = NULL;
   node.right = NULL;
   return node;
}
int main() {
   struct Graph g;
   struct GraphNode currentNode;
   /*read in the graph from top to bottom*/
   g.root = (GraphNode*) malloc(sizeof(GraphNode));
   *g.root = initNode(0, 3);
   //level 2 nodes
   g.root->left = (GraphNode*) malloc(sizeof(GraphNode));
   *g.root->left = initNode(1, 2);
   g.root->right = (GraphNode*) malloc(sizeof(GraphNode));
   *g.root->right = initNode(1, 4);
   //level 3 nodes
   (*g.root->left).left = (GraphNode*) malloc(sizeof(GraphNode));
   *(*g.root->left).left = initNode(2, 1);
   (*g.root->left).right = (GraphNode*) malloc(sizeof(GraphNode));
   *(*g.root->left).right = initNode(2, 2);
   (*g.root->right).left = (GraphNode*) malloc(sizeof(GraphNode));
   *(*g.root->right).left = initNode(2, 3);
   (*g.root->right).right = (GraphNode*) malloc(sizeof(GraphNode));
   *(*g.root->right).right = initNode(2, 5);
   /*DFS traversal*/
   Stack s;
   initStack(&s);
   push(&s, *g.root);
   while (!ifEmpty(&s)) {
       currentNode = top(&s);
        pop(&s);
        //mark as visited, here we simply print the graph node value out
       printf("(%d, %d)\n", currentNode.pvalue.h, currentNode.pvalue.w);
        //at most two children, left and right. As the binary tree is acyclic,
        // both nodes should not be visited yet, for cyclic graphs, 
        //one need additional methods to check if the nodes is visited or not before push
       if (currentNode.left != NULL) {
           push(&s, *currentNode.left);
       } 
       if (currentNode.right != NULL) {
           push(&s, *currentNode.right);
        } 
   }
   return 0;
}

3. Output

To compile the code in Linux, type the following command,

gcc stack.c dfs.c -o dfs

Then run the binary dfs,

        ./dfs

The output we’ll get is,

(0, 3)

(1, 4)

(2, 5)

(2, 3)

(1, 2)

(2, 2)

(2, 1)

which corresponds to the expected nodes visiting order in depth-first search. As we push the left node first, the traversal is from right to left.