Depth First Search (DFS) Algorithm

Video Tutorial
Depth First Search thumbnail
This video belongs to
Java DSA Course - Master the Fundamentals and Beyond
12 modules
Topics Covered


Depth First Search (DFS) is an algorithm that is mainly used to traverse the graph data structure. The algorithm starts from an arbitrary node (root node in case of trees) and explore as far as possible in the graph before backtracking.

After backtracking it repeats the same process for all the remaining vertices which have not been visited till now.

In this article, one of the main algorithm to traverse the graph have been discussed i.e. Depth First Search Algorithm (DFS).

It contains an example showing the working process of the DFS algorithm along with its code in three languages i.e. Java, C/C++, and Python. At last complexity, and applications of the algorithm have been discussed.

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.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 xx) 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 - DFS example

We can start our DFS process from any arbitrary vertex of the graph. Suppose we start our depth first search process from vertex AA, 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.i.e. either to go to vertex BB or vertex DD. Let's say we went to vertex BB now again we will go to one of its adjacent vertices.
  • We are having three choices i.e.i.e. either to go to vertex CC or vertex EE or back to vertex AA (because AA is also adjacent to vertex BB ) but we will consider going AA again because we had already visited it.
    Let's say we went to vertex EE, again from EE we need to go to one of its adjacent vertices.
  • Now at EE we have three choices i.e.i.e. either to go to vertex FF or vertex GG or vertex BB back but we will not consider it because it is already visited.
    Let's say we went to vertex FF.
  • From vertex FF we have only one unvisited node left i.e. vertex GG, so we will visit it.
  • We don't have any unvisited vertex adjacent to GG so we will go back to FF.
  • Now from FF also we don't have any choice so we will go back to EE and from EE the case is the same again so we will go back to BB.
  • From BB we have CC as an unvisited adjacent vertex so we will go to vertex CC and then from CC we will go to vertex DD as it is unvisited till now.
  • You can see now all the vertices have been traversed in the following order -- ABEFGCDA\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.


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

Pseudocode of DFS Algorithm

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

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 GraphGraph with following data members and methods.

Data Members -

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

Methods/Functions -

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

C/C++ implementation of DFS algorithm

Implementation of DFS algorithm

Python Implementation of DFS algorithm


The DFS traversal of the given graph starting from node 00 is - 00 11 44 55 66 22 11

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)O(V+E),O(V+2E)\simeq O(V+E), where VV is the number of vertices and EE is the number of edges in the given graph.
  • Space Complexity: O(V),O(V), because we need an auxiliary visited array/set of size VV.

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 DFSDFS 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 uu and vv 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.

Equip yourself to tackle complex C++ projects with confidence. Enroll in Data Structures in C++ Course by Scaler Topics now!

Wrapping Up

  • In this article, we have seen what is depth first search algorithm is, how it is implemented, and its time complexity.
  • We have seen how we can implement it, PseudoCode along with codes in two main languages viz. Java and C/C++ have been discussed.
  • Also in the bonus tip section, handling the corner cases involving the dis-connected graph has been explained.

See More