Depth First Search (DFS) Algorithm

Introduction of Depth First Seacrh (DFS) Algorithm

In Types of Graphs in Data Structure, we have seen what are the various type of data structures and how they differ from each other.

Now we will see how we can traverse the elements (nodes) of a given graph. Broadly, there are two methods to traverse the graph viz. BFS and DFS. Today we will see the complete DFS algorithm.

DFS stands for depth first search which is one of the main graph algorithms. As suggested by the name, the main idea of the DFS Algorithm is to go as deep as possible in the graph and to come back (backtrack) when there is no unvisited vertex remaining such that it is adjacent to the current vertex. Let's see how we can approach the depth first search algorithm.

Approach of DFS

The idea of the depth-first search algorithm is to start from an arbitrary node of the graph and to explore as far as possible before coming back $i.e.$ moving to an adjacent node until there is no unvisited adjacent node.

Then backtrack and check for other unvisited nodes and repeat the same process for them.

Here backtracking means, "When all the neighbors of a vertex (say $x$) are visited, the algorithm ends for vertex x so we return and check neighbors of the vertex that initiated the call to vertex x"

Let us understand how we can traverse the graph using DFS Algorithm through the following example.

Depth First Search Example

Let this be the given undirected graph with 7 vertices and 8 edges -

We can start our DFS process from any arbitrary vertex of the graph. Suppose we start our depth first search process from vertex $A$, since need to go as deep as possible in the graph, therefore we will go to one of the adjacent vertices of A.

The only thing we must take care of during the DFS process is that "we must not visit already visited vertices again."

• We have two choices $i.e.$ either to go to vertex $B$ or vertex $D$. Let's say we went to vertex $B$ now again we will go to one of its adjacent vertices.
• We are having three choices $i.e.$ either to go to vertex $C$ or vertex $E$ or back to vertex $A$ (because $A$ is also adjacent to vertex $B$ ) but we will consider going $A$ again because we had already visited it.
  Let's say we went to vertex $E$, again from $E$ we need to go to one of its adjacent vertices.
• Now at $E$ we have three choices $i.e.$ either to go to vertex $F$ or vertex $G$ or vertex $B$ back but we will not consider it because it is already visited.
  Let's say we went to vertex $F$.
• From vertex $F$ we have only one unvisited node left i.e. vertex $G$, so we will visit it.
• We don't have any unvisited vertex adjacent to $G$ so we will go back to $F$.
• Now from $F$ also we don't have any choice so we will go back to $E$ and from $E$ the case is the same again so we will go back to $B$.
• From $B$ we have $C$ as an unvisited adjacent vertex so we will go to vertex $C$ and then from $C$ we will go to vertex $D$ as it is unvisited till now.
• You can see now all the vertices have been traversed in the following order -- $A\rightarrow B \rightarrow E \rightarrow F \rightarrow G \rightarrow C \rightarrow D$

Algorithm of DFS Algorithm

Given Input: Adjacency list of the given graph.

Required Output: DFS traversal of the given graph.

Procedure:

1. Create a recursive function that takes arguments as a boolean array $visited$ of size $V$ and index $u$ denoting the current node (when it will be called initially, $u$ will be 0 or any other user-defined value).
2. Mark the current node as visited $i.e.$ visited[u]=True.
3. Print the current node $i.e.$ Print(u)
4. Search for all the adjacent vertices $v$, of node $u$ and identify the unvisited ones.
   As soon as unvisited vertex adjacent to $u$ found make a DFS call with index as v.

Pseudocode of DFS Algorithm

For DFS we have used an auxiliary boolean array of size $V$ where $V$ is the number of vertices present in the given graph $G$.

The visited array will keep information about which vertices have been already visited and which are not.

If we do not include this as part of our algorithm we have no way to find whether the next vertex is visited or not and if we don't care about visited status we will get into an infinite loop (as then we will cycle between some pair of nodes indefinitely).

DFS Algorithm Implementation in C, C++, and Java

For implementing DFS it is better to define a class $Graph$ with following data members and methods.

Data Members -

• $adj$ - It is the adjacency list, which is used to store graph data structre.
• $V$ - It denotes the total number of vertices, also $adj.size()=V$

Methods/Functions -

• $insertEdge$ - A void type function which take two arguments $u$ and $v$. It will add an undirected edge between $u$ and $v$.
• $DFS$ - Again, a void type function with single argument as index of the node $u$. It will declare a boolean array $visited$ of size $V$ to hold information of already visited nodes.
  Then it will call another function $DFS\_helper$ with arguments as $u$ and $visited$.
• $DFS\_helper$ - A void type fnction with two arguments as index of the current node $u$ and $visited$ array.
  It will mark and print the current node $u$ and then search and call itself recursively for all the univisted vertices $v$ adjacent to $u$.

C/C++ implementation of DFS algorithm

Implementation of DFS algorithm

Python Implementation of DFS algorithm

Output

The DFS traversal of the given graph starting from node $0$ is - $0$ $1$ $4$ $5$ $6$ $2$ $1$

Complexity Analysis of DFS Algorithm

• Time complexity: Since we consider every vertex exactly once and every edge at most twice, therefore time complexity is $O(V+2E)\simeq O(V+E),$ where $V$ is the number of vertices and $E$ is the number of edges in the given graph.
• Space Complexity: $O(V),$ because we need an auxiliary visited array/set of size $V$.

Bonus Tip

The bonus tip here can be a savior for you, because it will save your code to fail on the edge cases. Because the above code is written by assuming that the provided graph is connected.

What if the given graph is disconnected in nature. If you don't know what do connected and disconnected graphs mean how do they differ please refer to - Connected and Disconnected Graphs.

The above given code will only print the vertices of the component to which starting vertex belongs to. To overcome this problem we will tweak our code a little so that it can print all the vertices of the graph no matter whether they are connected or not.

We only need to change the $DFS$ function of the code, and the change is shown below -

And that's it 😁, by including three more lines of code we can also handle disconnected graphs.

Applications of DFS Algorithm

There are numerous applications of the Depth first search algorithm in graph theory. DFS Algorithm can be used in solving most problems involving graphs or trees. Some of its popular applications are -

• Finding any path between two vertices $u$ and $v$ in the graph.
• Finding the number of connected components present in a given undirected graph.
• For doing topological sorting of a given directed graph.
• Finding strongly connected components in the directed graph.
• Finding cycles in the given graph.
• To check if the given graph is Bipartite in nature.

See More

• Depth First Search in Python
• DFS Program in C