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

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.

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_two

Dfs Step Four

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

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.

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.

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.

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 :

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

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

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

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.

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

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

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

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

dfs_step_1-1

Dfs Step 1 1

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

Output

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


By admin

Leave a Reply

%d bloggers like this: