Depth First Search

The DFS algorithm is to traverse the graph in such a way that it tries to go far from the root node. The stack is used in the implementation of the DFS. Let’s see how DFS search works with respect to the following graph.

As stated before, in DFS, nodes are visited by going through the depth of the tree from the starting node. If we do the depth first traversal of the above graph and print the visited node, it’ll be “A B E F C D”. DFS visits the root node and then its children nodes until it reaches the end node, i.e. E and F nodes, then moves up to the parent nodes.

Algorithm:

1. Push the root node in the Stack.
2. Loop until the stack is empty.
3. Peek the node of the stack.
4. If the node has visited child node, get the unvisited child node, mark it as traversed and push it on the stack.
5. If the node does not have any unvisited child nodes, pop the node from the stack.

Listing: Following program is showing the implementation of DFS.

/*
* C Program to Implement Depth First Search Traversal using Post Order
       50
      /  \
    20   30
   /  \    
  70  80
/  \    \
10  40   60    
(50, 20, 30, 70, 80, 10, 40, 60)
*/

#include <stdio.h>
#include <stdlib.h>

struct btnode {
    int value;
    struct btnode *l;
    struct btnode *r;
};

typedef struct btnode bt;
bt *root;
bt *new, *list;
bt *create_node();
void display(bt *);
void construct_tree();
void dfs(bt *);

void main()
{
    construct_tree();
    display(root);
    printf("\n");
    printf("Depth first traversal\n ");
    dfs(root);
}

/* Creates an empty node */
bt * create_node()
{
    new=(bt *)malloc(sizeof(bt));
    new->l = NULL;
    new->r = NULL;
}

/* Constructs a tree */
void construct_tree()
{
    root = create_node();
    root->value = 50;
    root->l = create_node();
    root->l->value = 20;
    root->r = create_node();
    root->r->value = 30;
    root->l->l = create_node();
    root->l->l->value = 70;
    root->l->r = create_node();
    root->l->r->value = 80;
    root->l->r->r = create_node();
    root->l->r->r->value = 60;
    root->l->l->l = create_node();
    root->l->l->l->value = 10;
    root->l->l->r = create_node();
    root->l->l->r->value = 40;      
}

/* Display the elements in a tree using inorder */
void display(bt * list)
{
    if (list == NULL)
    {
        return;
    }
    display(list->l);
    printf("->%d", list->value);
    display(list->r);
}

/* Dfs traversal using post order */
void dfs(bt * list)
{
    if (list == NULL)
    {
        return;
    }
    dfs(list->l);
    dfs(list->r);
    printf("->%d ", list->value);
}

Output:

->10->70->40->20->80->60->50->30
Depth first traversal
->10->40->70->60->80->20->30->50