Depth First Search (DFS) for a Graph

Filed Under: C Programming
DFS

Depth First Search (DFS) is an algorithm that searches a graph/tree, in a depth-wise manner.

There are many ways through which we can traverse through a graph.

The two most common methods that we can use are:

  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)

Both of these methods are recursive in nature.

The only difference is that a BFS first searches the breadth of the graph/tree, while a DFS searches from top to bottom first, before branching out.

Also, a Depth First Search will tell us if two nodes are reachable or not. If the algorithm terminates and we still haven’t found our answer, that means that the two nodes are not connected!

In this article, let us take a look at the DFS Algorithm in detail.

I will also show you an implementation of this algorithm in C so that you can get a programmer’s perspective on how you can write this algorithm.


The Depth First Search Algorithm

As I mentioned earlier, the depth-first search algorithm is recursive in nature.

So, if you want to look for an element in the graph, the DFS procedure will first go as deep as possible from the current node, until you cannot go any further.

When you hit a dead end, you simply move back and try to find deeper routes from any of those nodes.

You simply keep trying all these ‘deepest’ routes until you have exhausted all possibilities.

To apply this algorithm, we need to keep track of the path ‘history‘, that includes the current node visited, so that we can come back to that point.

Since this will try different paths from the path of visited nodes, it is very natural to use a Stack Data Structure.

To simplify things, I will show you how this algorithm works on a graph.

The Algorithm

Before we start our algorithm, let us have a stack of the nodes in the current path. Initially, it is empty.

  • If a node to be visited is not there in the stack, we push it onto the stack and mark the node as visited.
  • We then check if the current node matches our search criteria.
  • If it does, we are done!
  • Otherwise, we need to go to all the nodes adjacent to the current node.
  • We will visit all such nodes, in any random order, and keep searching.
  • If all adjacent nodes are already visited, it is a dead end. We must go to the previously visited node and pop the recent node from the stack.
  • The algorithm will terminate if all the nodes have been searched (stack is empty), or if we get our answer.

So this algorithm will search the whole graph and is thus a good way to check if a path exists between two nodes.

An Example – Searching for a vertex

Let’s search for the vertex 7 in the graph below, using DFS.

When we begin at the start node (6), we mark it as visited, and add it to the stack.

Dfs Step One
Dfs Step One

Since this is not the node we want, we will visit all its unvisited adjacent nodes, and keep going until we hit a dead end.

Since the order doesn’t matter to us, let’s visit vertex 2 next. (We can also choose vertex 5)

Dfs Step Two
Dfs Step Two

Now, again, since it is not the destination vertex, let’s again visit all unvisited adjacent nodes of 2. Let’s choose 14.

Dfs Step Three
Dfs Step Three

Again, this is not the destination node. But now, this is a dead-end, since it does not have any adjacent node.

So, we must go back a step, and pop 14 from the stack. We are now at vertex 2 again.

Dfs Step Four
Dfs Step Four

Now, we move onto the node 7. Since this is the destination node, we are done!

Dfs Last Step
Dfs Last Step

Hopefully, you can now understand how DFS works. Let’s now move onto a C implementation!


Implementation of Depth First Search

We will use the code from our previous article on Graph Theory as a template, and build on from that.

I’ll be adding to this code. So let’s first quickly implement a stack using Linked Lists.

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

typedef struct Graph Graph;

typedef struct Node Node;

struct Node {
    // To represent the linked list node.
    // Contains the vertex index
    int vertex;
    // Vertex Key
    int key;
    // And a pointer to the next element in the linked list
    Node* next;
};

struct Graph {
    // Key List
    int* key_list;
    // Number of vertices
    int v;
    // Array of Adjacency Lists
    Node** adj_lists;
};

// Define the Stack here
typedef struct StackNode StackNode;

struct StackNode{
    // Stack of integers
    int data;
    StackNode* next;
};

int is_empty(StackNode* stack) {
    // Check if stack is empty
    if (!stack)
        return 1;
    return 0;
}

StackNode* push(StackNode* stack, int data) {
    // Pushes the data into the stack
    StackNode* node = (StackNode*) malloc (sizeof(StackNode));
    StackNode* temp = stack;
    node->data = data;
    node->next = temp;
    stack = node;
    return stack;
}

StackNode* pop(StackNode* stack) {
    // Pops the head of the stack
    if (!stack)
        return NULL;
    StackNode* temp = stack;
    stack = stack->next;
    temp->next = NULL;
    free(temp);
    return stack;
}

int top(StackNode* stack) {
    // Return the top of the stack
    if (!stack)
        return INT_MIN;
    return stack->data;
}

StackNode* init_stack(int data) {
    // Initializes the stack
    StackNode* stack = (StackNode*) malloc (sizeof(StackNode));
    stack->data = data;
    stack->next = NULL;
    return stack;
}

void free_stack(StackNode* stack) {
    // Free the stack
    if (!stack)
        return;
    StackNode* temp = stack;
    stack = stack->next;
    temp->next = NULL;
    free(temp);
    free_stack(stack);
}

void print_stack(StackNode* stack) {
    if (!stack)
        return;
    StackNode* temp = stack;
    printf("Stack: \n");
    while(temp) {
        printf("Data: %d -> ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

We’ll now show the code for building the graph. Since we denote each vertex using an index as well as its key value, the Node structure looks like this.

struct Node {
    // To represent the linked list node.
    // Contains the vertex index
    int vertex;
    // Vertex Key
    int key;
    // And a pointer to the next element in the linked list
    Node* next;
};

The rest of the code is almost the same as that of the previous article, except that we’ll also be adding in the key for every vertex.

// Adjacency Lists for the Graph
Node** init_adjacency_lists(Graph g) {
    // Initializes an adjacency matrix for the graph
    if (g.adj_lists)
        return g.adj_lists;
    // Allocates memory for the lists
    // There is a list for every vertex in the graph
    // which means there are g.v adjacent lists
    Node** adj_lists = (Node**) calloc (g.v,  sizeof(Node*));

    // Set them to NULL initially
    for (int i = 0; i < g.v; i++)
        adj_lists[i] = NULL;
    
    printf("Initialized Adjacency Lists!\n");
    return adj_lists;
}

void free_list(Node* list) {
    // Frees all nodes in the list, headed by 'list'
    Node* temp = list;
    while(temp) {
        Node* rm_node = temp;
        temp = rm_node->next;
        rm_node->next = NULL;
        free(rm_node);
    }
}

void free_adj_lists(Graph g) {
    // Free the adjacency matrix
    if (!g.adj_lists)
        return;
    for (int i=0; i<g.v; i++)
        free_list(g.adj_lists[i]);
    free(g.adj_lists);
}

void print_list(Node* list) {
    // Prints the linked list
    Node* temp = list;
    while(temp) {
        printf("Node: %d, Key: %d -> ", temp->vertex, temp->key);
        temp = temp->next;
    }
    printf("\n");
}

Node* create_node(int vertex, int key) {
    // Creates a LinkedList node to hold the vertex
    Node* node = (Node*) calloc (1, sizeof(Node));
    node->next = NULL;
    node->vertex = vertex;
    node->key = key;
    return node;
}

void add_edge(Graph g, int i, int j) {
    // Adds an edge connecting two vertices i and j
    if (!g.adj_lists) {
        fprintf(stderr, "Adjacency Lists not initialized!\n");
        exit(1);
    }
    
    else if (i > g.v || j > g.v) {
        fprintf(stderr, "Invalid Vertex Number\n");
        exit(1);
    }

    // Create the new node in the souce vertex
    // adjacency list and add the destination
    // vertex to it
    
    // Create a node containing the dst vertex index
    Node* node = create_node(j, g.key_list[j-1]);

    // Insert at the source list
    // Let's insert at the top, since it doesn't
    // matter whether we insert at the head or not
    node->next = g.adj_lists[i-1];
    // Make the new node as the head
    g.adj_lists[i-1] = node;
}

void remove_edge(Graph g, int i, int j) {
    // Sets the edge from i to j as zero
    if (!g.adj_lists) {
        fprintf(stderr, "Adjacency Lists not initialized!\n");
        exit(1);
    }
    // Search for vertex j in i's adjacency list
    Node* temp = g.adj_lists[i-1];
    if (!temp) {
        return;
    }
    if (!(temp->next)) {
        if (temp->vertex == j) {
            free(temp);
            g.adj_lists[i-1] = NULL;
        }
        return;
    }
    while (temp->next) {
        if (temp->vertex == j) {
            // We have found an edge! Remove this element.
            Node* rm_node = temp;
            temp->next = rm_node->next;
            rm_node->next = NULL;
            free(rm_node);
            return;
        }
        temp = temp->next;
    }
    // No element found :(
    return;
}

int check_if_exists(Graph g, int i, int j) {
    // Checks if there is an edge from vertex i to j
    if (!g.adj_lists) {
        fprintf(stderr, "Adjacency Lists not initialized!\n");
        exit(1);
    }
    else if (i > g.v || j > g.v) {
        fprintf(stderr, "Invalid Vertex Number\n");
        return 0;
    }
    
    // Search for vertex j in i's adjacency list
    Node* temp = g.adj_lists[i-1];
    if (!temp) {
        return 0;
    }
    if (!(temp->next)) {
        if (temp->vertex == j) {
            return 1;
        }
        return 0;
    }
    while (temp->next) {
        if (temp->vertex == j) {
            // We have found an edge! Remove this element.
            return 1;
        }
        temp = temp->next;
    }
    // No element found :(
    return 0;
}

Let’s now move onto the main part: the DFS() function.

The DFS() Functions

Now, it is often common practice to write a recursive function within another wrapper function. So our core DFS algorithm will be wrapped around a function called DFS(), which calls it under the hood.

This will check whether a path exists from the start_vertex to our destination vertex, specified by it’s key.

So it’s signature is :

int DFS(Graph g, int start_vertex, int key);

We’ll keep track of the visited nodes using an array of integers int* visited_list. Initially, this is set to Zero.

// g.v -> Number of Vertices
// This is initialized to zero using calloc()
int* visited_list = (int*) calloc (g.v, sizeof(int));

We also need to set up the stack for the DFS Algorithm.

// Initialize a stack with the key of the starting vertex
StackNode* stack = init_stack(g.key_list[start_vertex-1]);

Now, we are ready to call the main algorithm function DFS_recursive().

int ret_val = DFS_recursive(g, start_vertex, key, &stack, visited_list, 0);

This takes all the required parameters above. We also have one more parameter called start, which will push to the stack only if it is called recursively.

NOTE: We pass the stack address to DFS_recursive(), since otherwise, it will get overwritten, since it is simply a variable. Passing it as a pointer will preserve the stack during such recursive calls.

int DFS(Graph g, int start_vertex, int key) {
    // Performs a DFS on the Graph from start_vertex
    // and returns 1 if the destination key is found
    printf("Start Vertex: %d, Key: %d\n", start_vertex, g.key_list[start_vertex - 1]);
    if (g.key_list[start_vertex-1] == key) {
        return 1;
    }
    
    // Keep a visited list of nodes
    int* visited_list = (int*) calloc (g.v, sizeof(int));

    // Perform the DFS
    StackNode* stack = init_stack(g.key_list[start_vertex-1]);
    int ret_val = DFS_recursive(g, start_vertex, key, &stack, visited_list, 0);

    // Free Stuff and exit
    free_stack(stack);
    free(visited_list);
    return ret_val;
}

Now, let’s go to the DFS_recursive() function.

This pushes the current node to the stack and marks it as visited.

if (start)
    *stack = push(*stack, g.key_list[start_vertex-1]);

printf("Current Node: key: %d\n", g.key_list[start_vertex - 1]);
// Mark the current node as visited
visited_list[start_vertex - 1] = 1;

Now, we use the exact same algorithm that we mentioned above, in the example graph.

int DFS_recursive(Graph g, int start_vertex, int key, StackNode** stack, int* visited_list, int start) {
    // Recursive DFS function that is used to perform DFS()
    if (start)
        *stack = push(*stack, g.key_list[start_vertex-1]);

    printf("Current Node: key: %d\n", g.key_list[start_vertex - 1]);
    // Mark the current node as visited
    visited_list[start_vertex - 1] = 1;

    // While the stack is not empty
    while (!is_empty(*stack)) {
        if (g.key_list[start_vertex - 1] == key) {
            return 1;
        }
        else {
            // Not found. Go to the next node
            Node* node = g.adj_lists[start_vertex - 1];
            if (!node) {
                // Dead End. Go back after popping current node
                *stack = pop(*stack);
            }

            while (node) {
                // If any of it's neighbours are not visited
                if(visited_list[node->vertex - 1] == 0) {
                    // Go to that node and do a DFS from that node
                    if (DFS_recursive(g, node->vertex, key, stack, visited_list, 1) == 1)
                        return 1;
                    else {
                        // Pop the recently visited neighbour from the stack
                        *stack = pop(*stack);
                    }
                }
                node = node->next;
            }
        }
    }

    return 0;  
}

Now, that completes our DFS functions. Let’s now test it for our example graph.

Dfs Step 1 1
Dfs Step 1 1
void dfs_print(Graph g, int src, int dst) {
    // Find the vertex for the src key
    int start = -1;
    for (int i=0; i<g.v; i++) {
        if (g.key_list[i] == src)
            start = i + 1;
    } 
    if (start == -1) {
        fprintf(stderr, "Error: Key %d not found\n", src);
        return;
    }
    printf("Performing DFS on the Graph...\n");
    int ret_val = DFS(g, start, dst);
    if (ret_val == 1)
        printf("Key: %d is found!\n", dst);
    else
        printf("Key: %d is not found.\n", dst);
}

int main() {
    // Graph with 6 vertices
    int vertex_list[] = {6, 2, 5, 14, 7, 1};
    Graph g = {vertex_list, 6, NULL};
    printf("Created a Graph Structure with %d vertices\n", g.v);
    g.adj_lists = init_adjacency_lists(g);

    // Let's connect the 6 vertices using edges
    add_edge(g, 1, 2);
    add_edge(g, 1, 3);
    add_edge(g, 2, 4);
    add_edge(g, 2, 5);
    add_edge(g, 3, 6);
    add_edge(g, 6, 5);

    // Print the Adjacency Lists
    for (int i=0; i<g.v; i++) {
        printf("Vertex: %d , Key: %d => ", i+1, g.key_list[i]);
        print_list(g.adj_lists[i]);
    }

    // Print a Depth First Search from 6 to 14
    printf("\n");
    dfs_print(g, 6, 7);
    printf("\n");
    dfs_print(g, 6, 8);
    printf("\n");
    dfs_print(g, 6, 14);
    printf("\n");
    free_adj_lists(g);
    return 0;
}

The full code can be downloaded from the below section. When you compile the complete code, you’ll get the following output.

Output

Created a Graph Structure with 6 vertices
Initialized Adjacency Lists!
Vertex: 1 , Key: 6 => Node: 3, Key: 5 -> Node: 2, Key: 2 -> 
Vertex: 2 , Key: 2 => Node: 5, Key: 7 -> Node: 4, Key: 14 -> 
Vertex: 3 , Key: 5 => Node: 6, Key: 1 -> 
Vertex: 4 , Key: 14 => 
Vertex: 5 , Key: 7 => 
Vertex: 6 , Key: 1 => Node: 5, Key: 7 -> 

Performing DFS on the Graph...
Start Vertex: 1, Key: 6
Current Node: key: 6
Current Node: key: 5
Current Node: key: 1
Current Node: key: 7
Key: 7 is found!

Performing DFS on the Graph...
Start Vertex: 1, Key: 6
Current Node: key: 6
Current Node: key: 5
Current Node: key: 1
Current Node: key: 7
Current Node: key: 2
Current Node: key: 14
Key: 8 is not found.

Performing DFS on the Graph...
Start Vertex: 1, Key: 6
Current Node: key: 6
Current Node: key: 5
Current Node: key: 1
Current Node: key: 7
Current Node: key: 2
Current Node: key: 14
Key: 14 is found!

This shows that our code indeed works properly! It also prints the path of the search, so this will give you more insight into what it is doing.


Download the Code

The Code is available as a Github Gist. I have tried my best to avoid errors and make the code as clear as possible, but if you spot any, please do mention them to me!


Conclusion

Hopefully, you’ve understood what the DFS Algorithm does, using the example and the implementation that we showed you. If you have any doubts or suggestions, please do mention them in the comment section below. Until next time!


References


Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages