# Depth First Search (DFS) for a Graph

Filed Under: C Programming 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:

• 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.

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)

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

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.

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

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;
};

// 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
// Initializes an adjacency matrix for the graph
// 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++)

}

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);
}
}

return;
for (int i=0; i<g.v; i++)
}

void print_list(Node* 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
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
// 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
// Make the new node as the head
}

void remove_edge(Graph g, int i, int j) {
// Sets the edge from i to j as zero
exit(1);
}
// Search for vertex j in i's adjacency list
if (!temp) {
return;
}
if (!(temp->next)) {
if (temp->vertex == j) {
free(temp);
}
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
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
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 {
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.

```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) {
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
}

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);

// Let's connect the 6 vertices using edges

for (int i=0; i<g.v; i++) {
printf("Vertex: %d , Key: %d => ", i+1, g.key_list[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");
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
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

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.

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

close
Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors