DFS in Data Structure: Depth-First Search Algorithm Explained
Updated on Jun 17, 2025 | 19 min read | 11.61K+ views
Share:
For working professionals
For fresh graduates
More
Updated on Jun 17, 2025 | 19 min read | 11.61K+ views
Share:
Table of Contents
Did you know? There’s a fresh take on the DFS algorithm called Piecemeal-DFS, designed to tackle energy and resource constraints head-on! This approach breaks down the traditional DFS into multiple shorter routes, each no longer than a specified limit. The result? Fewer routes are needed to cover all the tree's edges. |
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.
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.
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:
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.
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.
Here are the detailed DFS in data structure algorithm steps that outline the implementation of DFS in data structure traversal:
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:
The time complexity of Depth-First Search (DFS) is:
Explanation:
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.
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:
The space complexity of Depth-First Search (DFS) is:
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.
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.
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.
Each graph vertex is assigned to one of two groups in a typical DFS implementation:
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.
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:
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:
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
The iterative Depth-First Search (DFS) method uses a stack data structure. The process of this stack-based DFS approach is as follows:
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:
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 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.
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:
Visits the current node first, then recursively traverses the left subtree, followed by the right subtree.
Traversal Order: A → B → C → D → E
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
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.
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:
Step |
Action |
Stack State |
Visited Nodes |
1 |
Start at A. Mark A as visited and push it onto the stack. |
[A] |
{A} |
2 |
Pop A. Visit its first unvisited neighbor B. Mark B and push it. |
[B] |
{A, B} |
3 |
Pop B. Visit its unvisited neighbor D. Mark D and push it. |
[D] |
{A, B, D} |
4 |
Pop D. No neighbors left. Backtrack to B (stack is now empty). |
[] |
{A, B, D} |
5 |
Backtrack to A. Pop A again and visit its next unvisited neighbor C. Mark C and push it. |
[C] |
{A, B, C, D} |
6 |
Pop C. Visit its unvisited neighbor E. Mark E and push it. |
[E] |
{A, B, C, D, E} |
7 |
Pop E. No neighbors left. Stack is empty. Traversal complete. |
[] |
All nodes visited |
Final DFS Traversal Order: A → B → D → C → E
Key Observations from the DFS Example:
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.
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.
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.
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:
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:
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
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.
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.
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.
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.
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.
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.
Master in-demand Software Development skills like coding, system design, DevOps, and agile methodologies to excel in today’s competitive tech industry.
Stay informed with our widely-read Software Development articles, covering everything from coding techniques to the latest advancements in software engineering.
Reference:
https://link.springer.com/article/10.1007/s00453-024-01275-8
900 articles published
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 s...
Get Free Consultation
By submitting, I accept the T&C and
Privacy Policy
India’s #1 Tech University
Executive PG Certification in AI-Powered Full Stack Development
77%
seats filled
Top Resources