DFS in Data Structure: Depth-First Search Algorithm Explained

Depth-First Search (DFS) is a key traversal technique for trees and graphs. Unlike breadth-first search, DFS prioritizes depth. It dives deep into a branch before backtracking. DFS uses a stack, either through recursion or explicitly. It is essential for applications like pathfinding, cycle detection, puzzle solving, and network analysis. DFS efficiently explores all possible paths in a graph or tree to solve complex problems.

In this blog, you’ll explore the DFS in data structure, comparing recursive and iterative approaches. We’ll also examine its time and space complexities and explore advanced applications like cycle detection, topological sorting in DAGs, and AI optimization for practical insights.

Depth-First Search (DFS): Core Features You Should Know

DFS in data structure is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It is implemented using recursion or an explicit stack and is efficient in terms of time complexity O(V+E), where V is vertices and E is edges. Its versatility makes it essential in both directed and undirected graphs for deep exploration and problem-solving.

With the increasing demand for experts in graph algorithms and problem-solving, now is the time to level up, explore these top courses to master in-demand skills.

• Executive PG Certification in AI-Powered Full Stack Development
• Master’s Degree in Artificial Intelligence and Data Science
• Professional Certificate Program in Cloud Computing and DevOps

DFS is a great option when the objective is to thoroughly explore a structure, particularly one with numerous possible paths, due to its deep exploration. 

The key features of depth-first search algorithms are as follows:

• Depth-first traversal in Trees or Graphs: DFS in data structure works by recursively calling itself to explore deeper into a structure. It follows one path as far as possible before backtracking.
• Memory efficiency: Compared to breadth-first search (BFS), DFS requires less memory since it processes one branch at a time rather than storing all nodes at a particular depth.
• Path exploration: DFS ensures that every node is visited, making it useful for solving puzzles, traversing decision trees, and exploring mazes.
• Backtracking capability: DFS is particularly valuable in constraint-based problems, such as maze solving, puzzle generation, and implementing algorithms like Sudoku solvers and N-Queens solutions.

Handling Cycles: In graphs with cycles (loops), DFS in data structure marks visited nodes to avoid revisiting them and prevent infinite loops.

Also Read: Understanding Tree Traversal in Data Structures

With a clear understanding of DFS's core features, it's time to explore how this powerful algorithm functions in practice, navigating graphs efficiently.

How Does DFS Work?

Depth-first search explores the edges that come out of the most recently discovered vertex; let’s call it s. The algorithm traverses these edges to visit the unexplored vertices. When all of the s’s (the discovered vertex's) edges are explored, the search backtracks until it reaches an unexplored vertex.

This process continues until all vertices that are reachable from the original source vertex are visited and discovered. If there are any unvisited vertices, the algorithm selects one of them as a new source and repeats the search from that vertex. The algorithm continues until all vertices are discovered.

The key thing to consider is ensuring that every vertex is visited once. Also, DFS in data structure uses a stack data structure (either explicitly or via recursion) to keep track of the vertices to visit next.

Steps of DFS Algorithm

Here are the detailed DFS in data structure algorithm steps that outline the implementation of DFS in data structure traversal:

• Step 1: Create an empty stack and a list to keep track of visited nodes.
• Step 2: Select any vertex to start the traversal. Push that vertex onto the stack and mark it as visited.
• Step 3: While the stack is not empty:
      - Look at the top node in the stack.
      - If it has any unvisited neighbors:
          • Pick one, push it onto the stack, and mark it as visited.
      - If no unvisited neighbors remain, remove (pop) the node from the stack and backtrack.
• Step 4: Repeat this process until all reachable nodes are visited and the stack is empty.

Complexity of DFS Algorithm

The amount of time an algorithm takes in relation to the amount of input it gets is referred to as its time complexity. A function called space complexity indicates how much memory (space) an algorithm needs in relation to the amount of input it receives. Let’s examine the time and space complexities for DFS implementation in programming:

1. Time Complexity of DFS in Data structure

The time complexity of Depth-First Search (DFS) is:

• O(V + E)
  Where:
  • V = Number of vertices (nodes)
  • E = Number of edges

Explanation:

• DFS visits each vertex exactly once.
• Each vertex explores all its adjacent edges exactly once.
• Hence, the overall time complexity becomes proportional to the total number of vertices (V) plus the total number of edges (E).

This complexity applies to standard graph representations such as adjacency lists. If an adjacency matrix is used, the complexity becomes O(V²), as DFS must scan an entire row (or column) for each vertex.

2. Space Complexity of DFS in Data structure

The space complexity of Depth First Search (DFS) varies based on the structure of the graph or tree being traversed. Below are the main considerations:

• General Case: 

The space complexity of Depth-First Search (DFS) is:

• O(V) 

Where: V = Number of vertices (nodes)

This is because, in the worst case, the recursion stack (for recursive DFS) or the explicit stack (in iterative DFS) can grow up to the number of vertices, particularly in linear chain-like structures.

• Tree Structure:

For trees, the space complexity is typically described as O(h), where h is the height of the tree. Since DFS dives deep along each branch before backtracking, the maximum depth of the recursion or explicit stack corresponds to the height of the tree.

• Special Case:

In certain scenarios, especially when dealing with search trees that have a defined branching factor, the space complexity may be noted as O(bm), where b is the branching factor, and m is the maximum depth of the search tree. However, this notation is more common in specialized contexts like AI search algorithms rather than standard graph or tree traversals.

For typical graph or tree traversal, the most widely cited space complexity for DFS is O(V).

Also Read: Time and Space Complexity in Data Structure: A Detailed Guide

Now that we understand how DFS in data structure works, let's explore the different methods of implementing this algorithm to achieve efficient graph traversal.

Different Approaches to Implement DFS Algorithm

Each graph vertex is assigned to one of two groups in a typical DFS implementation:

• Not Visited
• Visited
• In some implementations, a third state (Being Visited) tracks nodes currently in the recursion or stack, helping detect cycles.

The Depth-First Search algorithm's goal is to explore all reachable nodes while avoiding cycles. DFS in data structure can be implemented in two main ways: Recursive Approach and Iterative Approach

The iterative DFS method uses an explicit stack instead of recursion. The algorithm pushes the starting node onto the stack and explores nodes by popping them off the stack and adding their unvisited neighbors. This process continues until the stack is empty. Compared to the recursive method, the iterative method provides better memory control and avoids deep recursion issues.

1. Recursive Approach

The recursive method uses function calls. For every unvisited neighbor, the DFS algorithm recursively calls itself. This process is similar to navigating a maze: you take one route until you reach a dead end, then backtrack and try a different route.

The DFS algorithm tracks visited nodes to prevent infinite loops. While this method is simple and intuitive, it may consume more memory in deep graphs due to recursive function calls.

The recursive DFS in data structure works as follows:

1. Start at the given node.
2. Mark it as visited.
3. Recursively call DFS for each unvisited neighbor.
4. Backtrack when no unvisited neighbors remain.
5. Continue until all reachable nodes are visited.

This recursive DFS in the data structure tracks nodes through the call stack. When there are no unvisited neighbors, the recursion ends.

Example

Assume A, B, C, and D are nodes in a graph. You start with node A:

• Start at A and mark it as visited.
• Move to an unvisited neighbor, B, and mark it as visited.
• Proceed to another unvisited neighbor of B, C, and mark it as visited.
• If C has no unvisited neighbors, backtrack to B, then to A.
• Finally, visit any remaining unvisited nodes, such as D.

This procedure ensures that every path is explored before backtracking.

Code for implementing DFS in data structure using recursion: 

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

    def __eq__(self, other):
        return self.value == other.value  # Compare nodes based on their value

    def __hash__(self):
        return hash(self.value)  # Use the node's value to hash it

def add_edge(parent, child):
    parent.children.append(child)

def recursive_dfs(node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node.value, end=" ")  # Process the node
    for child in node.children:
        if child not in visited:
            recursive_dfs(child, visited)

# Example usage
if __name__ == "__main__":
    # Create nodes
    A = Node('A')
    B = Node('B')
    C = Node('C')
    D = Node('D')
    E = Node('E')
    
    # Add edges
    add_edge(A, B)
    add_edge(A, C)
    add_edge(B, D)
    add_edge(C, E)
    
    print("Recursive DFS Traversal:")
    recursive_dfs(A)

Output:

The example creates a graph with the following structure:

 A
  / \
  B   C
  |   |
  D   E

The DFS traversal starts at node 'A'. The output will be:

Recursive DFS Traversal:
A B D C E

The algorithm can be modified to keep track of the edges instead of vertices because each edge describes the nodes at each end. This strategy is useful when you are attempting to reconstruct the traversed tree after processing each node. 

In the case of a forest or group of trees, the algorithm can be expanded to include an outer loop that iterates over all the trees in order to process every single node.

Also Read: Recursion in Data Structures: Types & Components

2. Iterative Approach

The iterative Depth-First Search (DFS) method uses a stack data structure. The process of this stack-based DFS approach is as follows:

1. Push the starting node onto the stack.
2. While the stack is not empty:
   1. Pop a node from the stack.
   2. If the node has not been visited, mark it as visited.
   3. Push all unvisited neighbors onto the stack.
3. Repeat until all reachable nodes are visited.

By using an explicit stack, this method eliminates the overhead associated with recursive calls.

Example

Consider a graph with nodes A, B, C, and D:

• Push A onto the stack.
• Pop A, mark it as visited, and push its unvisited neighbors (B).
• Pop B, mark it as visited, and push its unvisited neighbors (C).
• Continue this process until all nodes have been visited.

The stack simplifies managing which nodes to visit next.

Python code for iterative DFS: 

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []
def add_edge(parent, child):
    parent.children.append(child)
def iterative_dfs(node):
    visited = set()
    stack = [node]
    while stack:
        current_node = stack.pop()
        if current_node not in visited:
            visited.add(current_node)
            print(current_node.value, end=" ")  # Process the node
            # Add neighbors to the stack in reverse order
            for child in reversed(current_node.children):
                if child not in visited:
                    stack.append(child)
# DFS traversal example
if __name__ == "__main__":
    # Create nodes
    A = Node('A')
    B = Node('B')
    C = Node('C')
    D = Node('D')
    E = Node('E')
    # Add edges
    add_edge(A, B)
    add_edge(A, C)
    add_edge(B, D)
    add_edge(C, E)
    print("\nIterative DFS Traversal:")
    iterative_dfs(A)

Sample Tree Structure:

The tree structure formed is:

      A
      / \
      B   C
    /     \
    D       E

Output:

Iterative DFS Traversal:
A C E B D

The iterative approach avoids recursion depth limits by manually handling the stack. This is useful for large trees or deep structures.  

Both iterative and recursive approaches achieve the same objective by using Depth-First Search (DFS) to explore all paths in a graph. Each method has its benefits. While the recursive method is simpler, it may require more memory in deep graphs. In contrast, the iterative approach provides better control over memory usage, particularly for balanced graphs.

Also Read: Types of Graphs in Data Structure & Applications

To understand the implementation of DFS, it's crucial to explore the different approaches that can be used, followed by a detailed look at the DFS traversal process.

DFS Traversal Process

DFS can be better understood through visualization, which illustrates how the algorithm traverses nodes hierarchically. By visually mapping DFS, it becomes clear how the algorithm prioritizes depth over breadth, exploring one path completely before backtracking.

DFS Tree Traversal

The Depth-First Search (DFS) algorithm starts at the root node and explores one branch as deeply as possible before backtracking to visit other branches. DFS-based tree traversal can be performed in three standard ways, depending on the order of visiting the root, left subtree, and right subtree:

1. Preorder Traversal (Root → Left → Right)

Visits the current node first, then recursively traverses the left subtree, followed by the right subtree.

Traversal Order: A → B → C → D → E

2. Inorder Traversal (Left → Root → Right)

Recursively visits all nodes in the left subtree first, processes the current node next, and finally traverses all nodes in the right subtree.

Traversal Order: B → A → D → C → E

3. Postorder Traversal (Left → Right → Root)

Recursively visits all nodes in the left subtree first, then all nodes in the right subtree, and finally processes the current node last.

Traversal Order: B → D → E → C → A

DFS ensures that each branch of a tree is fully explored before moving to another branch.

DFS Traversal on Graphs

Unlike trees, graphs can contain cycles and multiple connected components, making DFS traversal more complex. Here’s an example of DFS on a directed graph, starting from node A:

Step-by-Step DFS Traversal:

Final DFS Traversal Order: A → B → D → C → E

Key Observations from the DFS Example:

• DFS explores as deeply as possible before backtracking to explore other paths.
• A stack (explicit or recursive) ensures nodes are visited only when necessary.
• DFS guarantees all reachable nodes are visited but does not always find the shortest path (unlike BFS).
• For cyclic graphs, a "visited" list is necessary to prevent infinite loops.

Example Code:
def iterative_dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=" → ")
            visited.add(node)
            # Push neighbors in reverse order for preorder traversal
            for neighbor in reversed(graph[node]):
                stack.append(neighbor)
# Example graph
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}

iterative_dfs(graph, 'A')  # Output: A → B → D → C → E → 

Also Read: Types of Graphs in Data Structure & Applications

After understanding the DFS traversal process, it’s essential to be aware of frequent mistakes that can occur and how to avoid them for optimal performance.

Common Mistakes in DFS in Data Structure and How to Avoid Them?

While DFS is a powerful technique for traversing graphs and trees, it can lead to inefficiencies or incorrect results if certain challenges are not addressed. Recognizing and resolving these common mistakes is crucial for effective DFS implementation.

1. Infinite Loops
   • Problem: Failing to track visited nodes can cause DFS to revisit nodes, creating infinite loops.
   • Solution:
     • Use a "visited" set or list.
     • Mark nodes as visited immediately upon exploration.
     • Implement cycle detection for cyclic graphs.
2. Forgetting to Mark Nodes
   • Problem: Not marking nodes as visited leads to redundant visits and wasted resources.
   • Solution:
     • Use explicit data structures (e.g., boolean arrays, hash sets) to track visited nodes.
     • Ensure each node is processed only once.

This condensed version makes it easier to read and highlights the key points effectively.

Want to improve your coding efficiency? Explore upGrad's Data Structures & Algorithms course and sharpen your skills.

While avoiding common mistakes is crucial for DFS implementation, understanding its applications helps in deciding when and where to apply this algorithm effectively.

Applications of DFS in Data Structure

Developers primarily select a DFS in order to enable access to the same data from several places. For instance, a team that is separated over the globe must be able to access the same files in order to work together. DFS can be used in network analysis to help identify connectivity, detect deadlocks, and analyze network structures for routing and security. 

Let’s understand the use cases of DFS in data structure: 

1. Detecting Cycles in Graphs

The DFS technique is used to identify cycles in a directed graph. This is an essential task in applications such as dependency resolution and deadlock detection in operating systems. DFS produces a DFS tree (or a DFS forest in disconnected graphs), representing the graph’s vertices and edges.

When executing DFS on a disconnected graph, multiple trees are formed; thus, we use the term DFS Forest to refer to all of them. Each of these trees contains specific types of edges:

• Tree Edge 
• Forward Edge 
• Cross Edge 
• Back Edge

To identify a cycle in a directed graph, we focus solely on the Back Edge, which connects a vertex to one of its ancestors in the DFS tree.

Also Read: Top 30+ DSA projects with source code in 2025

2. Finding Connected Components

A directed graph is termed strongly connected if a path exists from every vertex to all other vertices. Strongly Connected Components (SCCs) represent a key concept in graph theory and algorithms. A Strongly Connected Component in a directed graph is a subset of vertices where each vertex can be reached from any other vertex within the same subset through directed edges.

Identifying SCCs can provide insights into a graph’s structure and connectivity, with applications in social network analysis, web crawling, and network routing. Kosaraju’s Algorithm, Tarjan’s Algorithm, and the DFS-based Condensation Graph approach are common methods for finding SCCs.

3. Topological Sorting

Topological Sorting is primarily used for scheduling tasks based on dependencies. In computer science, applications include instruction scheduling, determining formula cell evaluation sequences in spreadsheets, logic synthesis, arranging compilation tasks in makefiles, data serialization, and resolving symbol dependencies in linkers.

Topological sorting is only applicable to Directed Acyclic Graphs (DAGs). In DFS, a vertex is added to a stack after visiting all its descendants. The order in which vertices are popped from the stack gives the correct topological order.

4. Pathfinding in Mazes and Games

Mazes offer a traditional challenge. These situations highlight the strengths of Depth-First Search. DFS explores all potential paths to locate an exit. However, DFS does not guarantee the shortest path; Breadth-First Search (BFS) is generally more efficient for this purpose.

In video games, characters frequently navigate intricate settings. Developers use DFS to help characters explore dungeons or mazes. For example, a game might have a maze with multiple exits, and DFS examines each route until it finds a solution.

DFS is also used in robotics to map unknown environments. Robots equipped with sensors use DFS to explore new areas. However, real-world implementations often combine DFS with other techniques, such as A or Dijkstra’s Algorithm, for better efficiency.

5. Solving Puzzle Problems

Puzzles often require examining different possibilities. Depth-first search (DFS) is useful for solving Sudoku, jigsaws, and pathfinding challenges. By exploring every possible move, DFS ensures that all solutions are considered.

Many puzzle games use DFS. For example, in a game where the objective is to connect dots while avoiding crossing lines, DFS explores each connection possibility.

In strategy games like chess, DFS is used in the Minimax Algorithm to evaluate possible moves and outcomes, helping players strategize. DFS alone does not guarantee optimal solutions but is effective for exhaustive searches.

DFS is widely used in these situations. Because it can explore all routes, it remains a popular choice among engineers and developers.

By exploring DFS applications, you're building a solid base in data structures. Take your expertise to the next level with upGrad's comprehensive learning path in DFS and related fields.

Become an Expert in DFS and Data Structures with upGrad!

Mastering Depth-First Search (DFS) equips you with a powerful tool for solving complex graph and tree traversal problems. To apply DFS effectively, focus on both recursive and iterative methods, ensuring proper stack management and visited node tracking. Understanding its time complexity (O(V + E)) and space complexity (O(V)) is crucial for optimizing your approach, particularly in handling cycles and backtracking scenarios.

To further advance your skills, upGrad’s specialized courses provide expert-led guidance and practical experience. These courses bridge knowledge gaps and prepare you for practical applications. 

In addition to above mentioned specialized courses, here are some free foundational courses to get you started.

• Learn Basic Python Programming
• Data Structures and Algorithms
• Core Java Basics
• Advanced JavaScript for All
• Object-Oriented Analysis and Design for Beginners

Looking to advance your skills in DFS and data structure? Contact upGrad for personalized counseling and valuable insights into advanced technologies. For more details, you can also visit your nearest upGrad offline center.

Boost your career with our popular Software Engineering courses, offering hands-on training and expert guidance to turn you into a skilled software developer.

Explore our Popular Software Engineering Courses

Master in-demand Software Development skills like coding, system design, DevOps, and agile methodologies to excel in today’s competitive tech industry.

In-Demand Software Development Skills

Stay informed with our widely-read Software Development articles, covering everything from coding techniques to the latest advancements in software engineering.

Read our Popular Articles related to Software

Reference:
https://link.springer.com/article/10.1007/s00453-024-01275-8