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.
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#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.
|
1 2 3 4 5 6 7 8 9 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
// 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 Numbern"); 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 Numbern"); 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 :
|
1 |
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.
|
1 2 3 |
// 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.
|
1 2 |
// 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().
|
1 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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: %dn", 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.
|
1 2 3 4 5 |
if (start) *stack = push(*stack, g.key_list[start_vertex-1]); printf("Current Node: key: %dn", 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
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: %dn", 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
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 foundn", 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 verticesn", 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
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!