Depth-First Search (DFS)

In the previous lesson, we explored Breadth-First Search (BFS) and learned how it traverses a graph level by level.

While BFS expands outward evenly, there are situations where we want to go as deep as possible along a path before exploring alternatives.

This is where Depth-First Search (DFS) becomes useful.

What Is Depth-First Search?

Depth-First Search is a graph traversal algorithm that explores a path as far as it can before backtracking.

Instead of visiting all neighbors first, DFS chooses one neighbor and continues moving forward until no further progress is possible.

Only then does it backtrack and explore other paths.

Real-World Intuition

Imagine you are exploring a maze.

You pick one path and keep walking forward. If you hit a dead end, you walk back to the last junction and try a different route.

You do not check every nearby corridor first — you go deep into one direction.

This exploration strategy is exactly how DFS works.

How DFS Differs from BFS

Although both algorithms traverse graphs, their behavior is fundamentally different.

BFS focuses on breadth, while DFS focuses on depth.

This difference affects:

• Traversal order
• Memory usage
• Use cases

The Core Idea Behind DFS

The key data structure behind DFS is a stack.

A stack follows the rule:

Last In, First Out (LIFO)

DFS can be implemented using:

• An explicit stack
• Or recursion (which uses the call stack)

DFS Implementation (Recursive)

Let us apply DFS to the same graph used in BFS.

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

visited = set()

def dfs(graph, node):
    if node not in visited:
        print(node)
        visited.add(node)

        for neighbor in graph[node]:
            dfs(graph, neighbor)

dfs(graph, 'A')

This recursive approach allows DFS to go deep into one branch before returning.

Understanding the Traversal Order

Starting from node A, DFS will:

• Visit A
• Go to B
• Go to D
• Backtrack and then explore C

This order depends on how neighbors are listed in the adjacency structure.

Time and Space Complexity

Just like BFS, DFS runs in:

O(V + E)

Where:

• V = number of vertices
• E = number of edges

However, DFS may use more stack space if the graph is very deep.

When Should You Use DFS?

DFS is preferred when:

• You need to explore all possible paths
• You want to detect cycles
• You are solving backtracking problems

Algorithms such as maze solving, topological sorting, and puzzle solvers rely heavily on DFS.

Common Pitfalls in DFS

Some common mistakes include:

• Forgetting the visited check
• Causing infinite recursion in cyclic graphs
• Stack overflow in very deep graphs

Careful implementation avoids these issues.

Mini Practice

Think about exploring folders on your computer.

Do you open one folder completely before moving to the next?

That behavior closely resembles DFS.

Exercises

Quick Quiz

In the next lesson, we will use DFS concepts to learn cycle detection in graphs, a critical skill in real-world systems.