Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconSoftware Developmentbreadcumb forward arrow iconDFS (Depth First Traversal) in Data Structure: What is, Ordering & Applications

DFS (Depth First Traversal) in Data Structure: What is, Ordering & Applications

Last updated:
27th Jun, 2022
Read Time
7 Mins
share image icon
In this article
Chevron in toc
View All
DFS (Depth First Traversal) in Data Structure: What is, Ordering & Applications

Meaning of DFS in Data Structure

DFS in Data Structure, also known as depth-first traversal, is a recursive algorithm primarily used to search all the vertices of a graph or tree data structure. Traversal is the visiting of every node of a graph. The algorithm begins from the root node (which may be an arbitrary node as the root node in a graph) and goes as far as it can along each branch before backtracking. 

The idea is to begin from the root or arbitrary node and keep the node marked. After this, you need to move to the adjacent node that is unmarked and continue this loop until there is no unmarked adjoining node. Then backtrack and examine the other nodes that are unmarked and traverse them. The final step is to print the nodes within the path.


Formulate a recursive function that will take the node’s index and a visited array.

  1.   Keep the current node marked as visited and then print it.
  2. Traverse all the adjoined notes and the unmarked ones and call the recursive function with the adjacent node’s index.

Explore our Popular Software Engineering Courses


The analysis of time and space in the DFS in Data Structure varies according to its area of application. Theoretically, DFS is mainly used to cross a full graph and takes time O(|V|+|E|) where |V| depicts the number of vertexes and |E| depicts the number of edges. This graph is linear. 

Ads of upGrad blog

In these applications, space O(|V|) is also used as a last resort to keep the stack of vertices stored on the search path and the set of vertices that are already visited. Therefore, the time and space bounds setting are similar to the breadth-first search. Here, the two algorithms used are less dependent on their complexity and more on the various characteristics of the vertex orders produced by the two algorithms. 

When it comes to applications of DFS in Data Structure related to specific domains, like finding solutions in web-crawling or AI, the graph that requires traversing might be too substantial to visit in totality. In such cases, the search is only executed to a restricted depth; due to finite resources, like disk space or memory. Data structures aren’t typically used to track the set of all the vertices visited previously. A search performed to a restricted depth still makes the time linear when it comes to the unit of expanded edges and vertexes. 

However, remember that this number does not have the same size as the entire graph since some of the vertexes may be searched multiple times and others not searched.

In such instances, DFS also turns to heuristic methods for selecting a more promising branch. Finally, when the appropriate depth limit cannot be determined, a priori, iterative deepening DFS is repeatedly applied via a sequence of growing limits. 

Learn Software Development Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs or Masters Programs to fast-track your career.

Depth First Search Algorithm

Each vertex of a graph in a standard DFS implementation is divided  into either of two categories:

  1.   Not Visited
  2.   Visited

The algorithm is used to pinpoint each vertex and mark them as visited and at the same time avoid cycles.

 This is how the DFS algorithm works:

  1.   Put any particular vertex of the graph on a stack.
  2.   The item on top of the stack should be added to the visited list.
  3.   Make a list of adjoining nodes of that vertex and add those not in the visited list on the top of the stack.
  4.   Keep repeating the previous steps till the stack empties.

DFS ordering

Vertex orderings: There are four ways of linearly ordering the vertexes of a graph or tree in DFS:

  1. The list of the vertexes arranged how they were visited first by the DFS algorithm is known as pre-ordering. It is a concise way to describe the search’s progress.
  2. The list of the vertexes in the order that they were visited last by the algorithm is known as post-ordering.
  3. The list of the vertexes in the order opposite to their first visit is a reverse pre-ordering. Therefore, it should not be mistaken for post ordering.
  4. The list of the vertexes in the order opposite to their last visit is a reverse post-ordering. It should not be mistaken for pre-ordering.

Additionally, there is in-ordering and reverse in-ordering for binary trees.

Depth First Search or DFS for a Graph 

The DFS for a graph is almost the same as the DFS for a tree. The only difference is that the graphs may have cycles, unlike trees. A node might be visited multiple times and to avoid processing the node, a Boolean visited array is used. 

Output Of A Depth First Search

The depth-first search is more easily depicted in terms of a spanning tree of the vertexes that are already reached in the search. Based on this spanning tree, the original graph edges are divided into three classes: the forward edges where the node of the tree is pointed towards one of its descendants, the back edges where the node is pointed towards one of its ancestors, and cross edges, which does neither of the previous functions.

Applications Of Depth First Traversal (DFS)

Depth-first search is used in the following algorithms as a building block:

  •         Searching for components that are connected.
  •         Finding 2-(vertex or edge)-connected components.
  •         Finding the graph’s bridges.
  •         Finding 3-(vertex or edge)-connected components.
  •         Topological sorting.
  •         Finding components that are strongly connected.
  •         Finding out if a species is similar to one or another species in a phylogenetic tree.
  •         Planarity testing.
  •         Producing words to determine the limit set of any group.
  •         Solving puzzles that have only one solution, like mazes.
  •         Maze generation.
  •         Searching for bi-connectivity in graphs.

DFS Pseudocode and Implementation in Python

The init() function is run on every node in the pseudocode below to ensure that all the vertexes are visited. This is especially important as graphs might have various disconnected areas.

Here is the pseudocode:

DFS(G, u)

    u.visited = true

    for each v ∈ G.Adj[u]

        if v.visited == false


init() {

    For each u ∈ G

        u.visited = false

     For each u ∈ G

       DFS(G, u)


Here is the DFS implementation in Python:

graph = {

  ‘5’ : [‘3′,’7’],

  ‘2’ : [‘1’, ‘3’],

  ‘6’ : [‘7’],

  ‘3’ : [],

  ‘4’ : [‘6’],

  ‘7’ : []


visited = set()

def dfs(visited, graph, node): 

    if node not in visited:

        print (node)


        for neighbour in graph[node]:

            dfs(visited, graph, neighbour)

print(“This is the DFS:”)

dfs(visited, graph, ‘5’)


This is the DFS: 5

Explore our Popular Software Engineering Courses

The complexity of Depth First Search

Ads of upGrad blog

John Reif explored the computational complexity of Depth First Search. To be precise, in a graph, the given fact is G, let O be the standard order determined by the repetitive DFS algorithm. G represents the graph, and O represents the ordering output of the redundant DFS algorithm. This output is known as the lexicographic DFS ordering. 


The main goal of the DFS algorithm is visiting every single vertex that avoids cycles in target graphs. If you wish to get involved with advanced implementations of searching operations or ordering operations, you should definitely consider pursuing a premium and holistic course in Depth First Search and Data Structure.

upGrad has some top-tier DFS courses like Master of Science in Computer Science

 If you are struggling to take your next step and looking for some expert advice, upGrad Mentorship seeks to provide you with one-to-one sessions with the best career counsellors and experts in the industry.  


Pavan Vadapalli

Blog Author
Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working on solving problems of scale and long term technology strategy.

Frequently Asked Questions (FAQs)

11. What is the property or usage of a depth-first traversal?

The DFS or Depth First Search algorithm crosses a graph depthward and, to remember to obtain the next vertex for beginning a search, utilises a stack when it is met with a dead-end in an iteration.

22. Which data structure is used in depth-first traversal?

The data structure used for DFS is Stack. Stack is primarily used in any standard execution of DFS or Depth First Search.

33. What are the time and space requirements of the depth-first search algorithm?

O(|V|) is depicted as time complexity, where |V| is denoted as the number of nodes. All nodes must be traversed in this case. On the other hand, space complexity is also depicted as O(|V|) since in the ultimate scenario, all vertices need to be held in the queue.