Depth-First Search (DFS) – Full Explanation with Example

1. Introduction

Depth-First Search (DFS) is a fundamental algorithm used to explore nodes and edges of a graph. It starts at a source node and explores as far as possible along each branch before backtracking.

DFS is like exploring a maze by going as deep as possible down one path before trying another.

2. Key Concepts

• Graph: A collection of vertices (nodes) and edges.
• Directed vs Undirected Graph: DFS works for both types.
• Visited Nodes: To avoid cycles and repeated visits, a visited array/list/set is maintained.
• Recursion or Stack: DFS can be implemented using recursion or using a stack data structure.

3. DFS Algorithm (Pseudocode)

Recursive Version

DFS(node):
    mark node as visited
    for each neighbor of node:
        if neighbor is not visited:
            DFS(neighbor)

Iterative Version (Using Stack)

DFS(start):
    create a stack and push start node
    mark start as visited
    while stack is not empty:
        node = pop from stack
        for each neighbor of node:
            if neighbor is not visited:
                mark neighbor as visited
                push neighbor to stack

4. DFS Example

Let’s consider the following graph:

   A
  / \
 B   C
 |   |
 D   E

Adjacency List Representation

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

Recursive DFS Traversal (Starting from A)

visited = set()

def dfs(graph, node):
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor)

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

dfs(graph, 'A')

Output:

A B D C E

The order may vary depending on how neighbors are ordered in the list.

5. Iterative DFS in Python (Using Stack)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            # Add neighbors in reverse to mimic recursive order
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

dfs_iterative(graph, 'A')

6. DFS in a Matrix/Grid

Example: 2D Grid DFS

def dfs_grid(grid, x, y, visited):
    rows, cols = len(grid), len(grid[0])
    if x < 0 or y < 0 or x >= rows or y >= cols:
        return
    if (x, y) in visited or grid[x][y] == 0:
        return

    visited.add((x, y))

    # Explore 4 directions: up, down, left, right
    dfs_grid(grid, x+1, y, visited)
    dfs_grid(grid, x-1, y, visited)
    dfs_grid(grid, x, y+1, visited)
    dfs_grid(grid, x, y-1, visited)

grid = [
    [1, 1, 0],
    [0, 1, 0],
    [1, 0, 1]
]
visited = set()
dfs_grid(grid, 0, 0, visited)

7. Applications of DFS

• Pathfinding in Mazes
• Cycle Detection in Graphs
• Topological Sorting
• Finding Connected Components
• Solving Puzzles (e.g., Sudoku, N-Queens)
• Checking Bipartite Graph
• Artificial Intelligence (AI) Search Algorithms
• Maze solving algorithms

8. Time and Space Complexity

Let:

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

Time Complexity:

• O(V + E)
  Each node and edge is visited once.

Space Complexity:

• O(V) (for visited set and recursion stack in worst case)

9. Advantages and Disadvantages

Advantages:

• Simple to implement (especially recursively)
• Good for problems requiring backtracking
• Uses less memory compared to Breadth-First Search (BFS)

Disadvantages:

• Can get stuck going deep (in infinite or very deep graphs)
• Not guaranteed to find the shortest path (unlike BFS)

10. Summary Table