XQA
Back to Data Structures & Algorithms
2025-12-047 min read

DFS Algorithm (Data Structures & Algorithms)

Learn DFS Algorithm (Data Structures & Algorithms) step by step with clear examples and exercises.

Title: DFS Algorithm (Data Structures & Algorithms)

Why This Matters

The Depth First Search (DFS) algorithm is a fundamental graph traversal method used to explore and solve problems related to graphs, trees, and networks. It's essential for various applications such as finding connected components, detecting cycles, solving mazes, and more. In interviews, DFS is often used to test problem-solving skills and understanding of data structures and algorithms.

Prerequisites

To follow this lesson, you should have a good understanding of the following concepts:

  1. Basic Python syntax (variables, functions, loops, conditional statements)
  2. List data structure in Python
  3. Recursion
  4. Graphs and adjacency lists
  5. Binary trees and tree traversal
  6. Time complexity analysis

Core Concept

Definition

The Depth First Search algorithm explores a graph or tree by visiting as far as possible along each path on the current node, before backtracking. The key idea is to delve into unexplored areas as deeply as possible before backtracking and exploring other paths. DFS uses a stack (or recursion) for memory management during traversal.

DFS in Graphs

A graph consists of nodes (vertices) connected by edges. In an adjacency list representation, each node has a list of its adjacent nodes. DFS starts at an arbitrary node and explores as far as possible along each path until it reaches a dead end or visits all nodes. Once a node is visited, it is marked to avoid revisiting the same node during backtracking.

DFS in Trees

In a tree, DFS can be used to determine the depth of each node, find the height (maximum depth), and check if the tree is a binary search tree (BST). The basic idea remains the same: start at the root, explore as far as possible along each branch, and mark visited nodes during backtracking.

DFS in Binary Trees

In binary trees, DFS can be used to perform in-order, pre-order, and post-order traversals. Each traversal order has its own use cases, such as sorting elements in an in-order traversal or constructing a new tree from a given set of values in a post-order traversal.

DFS Algorithm Steps

  1. Start from an arbitrary node (or all nodes in case of connected components problem)
  2. Mark the current node as visited
  3. Explore all adjacent unvisited nodes recursively or using a stack (push them onto the stack before exploring their neighbors)
  4. If no more unexplored neighbors are found, pop the top node from the stack and move to its parent node (backtracking)
  5. Repeat steps 3-4 until all nodes have been visited or the entire graph/tree has been explored

DFS in Python

Here's a simple implementation of DFS for an undirected graph represented as an adjacency list:

def dfs(graph, node, visited=set()):
visited.add(node)
print(f"Visiting {node}")
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)

In this implementation, the dfs function takes a graph (represented as a dictionary where keys are nodes and values are lists of adjacent nodes), a starting node, and an empty set to keep track of visited nodes. The function recursively visits all unvisited neighbors of the current node until it runs out of unexplored neighbors or has visited all nodes in the graph.

Here's a simple implementation of DFS for a binary tree:

class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def dfs(root, visited=set()):
if root is None:
return

visited.add(root.value)
print(f"Visiting {root.value}")

if root.left:
dfs(root.left, visited)
if root.right:
dfs(root.right, visited)

In this implementation, the dfs function takes a binary tree represented as a recursive data structure and an empty set to keep track of visited nodes. The function visits each node in the tree and its subtrees, marking visited nodes along the way.

Worked Example

Let's consider the following undirected graph:

A -- B -- C
| |
D -- E -- F

Here's how DFS traverses this graph starting from node A:

  1. Start at node A (visited)
  2. Explore neighbor B (unvisited)
  3. Explore neighbor C (unvisited)
  4. Explore neighbor C's neighbor A (already visited, so backtrack)
  5. Backtrack to node C and explore its other neighbor D (unvisited)
  6. Explore neighbor E of node D (unvisited)
  7. Explore neighbor F of node E (unvisited)
  8. Backtrack to node E and explore its other neighbor F's neighbor B (already visited, so backtrack again)
  9. Backtrack to node D and explore its other neighbor C (already visited, so backtrack again)
  10. Backtrack to the initial node A and no more unexplored nodes remain in the graph

The output of this traversal would be:

Visiting A
Visiting B
Visiting C
Visiting D
Visiting E
Visiting F

Common Mistakes

  1. Not marking visited nodes: If you don't keep track of visited nodes, you might end up visiting the same node multiple times or missing some nodes entirely.
  2. Incorrect handling of cycles: DFS can get stuck in infinite loops when encountering cycles in a graph. To avoid this, mark each cycle as soon as it is detected and break out of the recursion.
  3. Not considering disconnected components: If you're solving problems related to connected components, make sure to handle graphs with multiple disconnected components separately.
  4. Incorrect implementation of DFS in trees: In a tree, the order in which nodes are visited doesn't matter as long as every node is visited and the tree structure remains intact. However, some implementations might not guarantee this.
  5. Misunderstanding the problem statement: Always make sure you understand the problem statement clearly before implementing DFS, as it can be used to solve a variety of problems in different ways.

Subheadings under Common Mistakes:

  • Marking Visited Nodes Properly
  • Handling Cycles Correctly
  • Accounting for Disconnected Components
  • Implementing DFS in Trees Correctly
  • Understanding the Problem Statement

Practice Questions

  1. Implement DFS for a directed graph represented as an adjacency list.
  2. Use DFS to check if a given tree is a binary search tree (BST).
  3. Write Python code to find all connected components of an undirected graph using DFS.
  4. Solve the maze problem using DFS.
  5. Implement DFS for detecting cycles in a directed graph.
  6. Implement DFS for performing in-order, pre-order, and post-order traversals on binary trees.
  7. Use DFS to find the height of a binary tree.
  8. Use DFS to determine if a given undirected graph is connected.
  9. Use DFS to solve the Hamiltonian Path Problem for a given graph.
  10. Implement DFS to find the shortest path between two nodes in an unweighted graph.

FAQ

  1. What is the time complexity of DFS? The time complexity of DFS is O(V + E), where V is the number of vertices (nodes) and E is the number of edges.
  2. How does DFS handle cycles in a graph? When DFS encounters a cycle, it marks the current node as visited and breaks out of the recursion to avoid getting stuck in an infinite loop.
  3. Can DFS be used for sorting? Yes, DFS can be used for topological sorting of directed acyclic graphs (DAGs) by visiting nodes in a specific order based on their dependencies.
  4. What is the difference between DFS and BFS? DFS explores a graph or tree as far as possible along each path before backtracking, while Breadth-First Search (BFS) explores all nodes at the same depth level before moving to the next level. Both algorithms have their own use cases depending on the problem at hand.
  5. How can DFS be used for graph coloring? DFS can be used to find a valid coloring of a graph by assigning colors to vertices such that no two adjacent vertices share the same color. This is known as Vertex Color Problem or Graph Coloring Problem, and it has various applications in scheduling, map coloring, and more.
  6. How does DFS handle disconnected components in a graph? When using DFS to find connected components of an undirected graph, each call to the dfs function will discover one connected component by exploring all reachable nodes from the starting node. To handle multiple disconnected components, you can make separate calls to the dfs function for each connected component or use a union-find data structure to efficiently merge connected components during traversal.
  7. Can DFS be used to find the shortest path between two nodes in a weighted graph? Yes, DFS can be used to find the shortest path between two nodes in a weighted graph using techniques like Bellman-Ford or Dijkstra's algorithm. However, these algorithms are more efficient and commonly used for finding the shortest paths in weighted graphs.
  8. Can DFS be used to solve the Traveling Salesman Problem (TSP)? Yes, DFS can be used as a subroutine in some TSP heuristics like Nearest Neighbor or 2-Opt. However, more efficient algorithms such as linear programming, dynamic programming, and genetic algorithms are commonly used for solving the TSP.
  9. Can DFS be used to find the maximum flow in a network? No, DFS is not suitable for finding the maximum flow in a network. Instead, algorithms like Ford-Fulkerson or Edmonds-Karp are more efficient and commonly used for solving maximum flow problems.
  10. Can DFS be used to find the minimum spanning tree of a graph? No, DFS is not suitable for finding the minimum spanning tree of a graph. Instead, algorithms like Kruskal's or Prim's are more efficient and commonly used for solving minimum spanning tree problems.
DFS Algorithm (Data Structures & Algorithms) | Data Structures & Algorithms | XQA Learn