Depth-First Search (DFS) - Complete Guide

Introduction

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It is a "blind" search, meaning it explores the graph without any specific direction or heuristic, prioritizing depth over breadth.

The Core Concept

Imagine you are exploring a maze. If you choose to go down the first corridor you see and keep walking until you hit a dead end, then backtrack to the last junction and try the next corridor, you are performing a DFS. This "go deep, then backtrack" strategy is the essence of DFS.

Graph Representation

Before implementing DFS, we need a way to represent the graph. The most common representation is the Adjacency List.

interface Graph {
  [key: string]: string[];
}

const graph: Graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

How DFS Works

DFS uses a Stack data structure (Last-In, First-Out) to keep track of the nodes to visit next. Alternatively, it can be implemented using Recursion.

1. Iterative Approach (Using Stack)

1. Push the starting node onto the stack.
2. While the stack is not empty:

a. Pop a node from the stack.

b. If the node has not been visited:

i. Mark it as visited.

ii. Print/process the node.

iii. Push all its unvisited neighbors onto the stack.

2. Recursive Approach

1. Mark the current node as visited.
2. Recursively call DFS for all adjacent nodes that haven't been visited.

Implementation

Iterative Implementation in TypeScript

function dfsIterative(graph: Graph, startNode: string): void {
  const visited = new Set<string>();
  const stack: string[] = [startNode];

  while (stack.length > 0) {
    const currentNode = stack.pop();

    if (currentNode && !visited.has(currentNode)) {
      visited.add(currentNode);
      console.log(`Visited: ${currentNode}`);

      // Push neighbors in reverse order to maintain left-to-right traversal
      for (const neighbor of graph[currentNode]) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

Recursive Implementation in TypeScript

function dfsRecursive(graph: Graph, node: string, visited: Set<string> = new Set()): void {
  if (visited.has(node)) {
    return;
  }

  visited.add(node);
  console.log(`Visited: ${node}`);

  for (const neighbor of graph[node]) {
    dfsRecursive(graph, neighbor, visited);
  }
}

Complexity Analysis

Time Complexity: O(V + E)

• V is the number of vertices (nodes).
• E is the number of edges.
• In the worst case, we visit every node and every edge exactly once.

Space Complexity: O(V)

• Stack Space: In the worst case (a linear chain graph), the stack or recursion depth will hold all V nodes.
• Visited Set: We store V nodes in the visited set.

Applications of DFS

1. Pathfinding: Finding a path between two nodes in a graph.
2. Topological Sorting: Ordering vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before v in the ordering.
3. Cycle Detection: Detecting cycles in a graph (both directed and undirected).
4. Connected Components: Finding all connected components in an undirected graph.
5. Maze Generation: Generating random mazes.

DFS vs. BFS

| Feature | Depth-First Search (DFS) | Breadth-First Search (BFS) |

| :--- | :--- | :--- |

| Data Structure | Stack (Iterative) or Recursion | Queue |

| Order of Traversal | Depth-first (go deep first) | Breadth-first (level by level) |

| Memory Usage | Lower (only stores path to root) | Higher (stores all nodes at current level) |

| Best For | Finding paths in deep graphs, Topological Sort | Shortest path in unweighted graphs, Finding nodes at a specific level |

Common Use Cases in Interviews

1. Number of Islands: Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
2. Clone Graph: Clone an undirected graph.
3. Course Schedule: Determine if you can finish all courses given prerequisites.
4. Surrounded Regions: Replace all 'O's surrounded by 'X's with 'X's.

Common Pitfalls

1. Infinite Loops: Forgetting to mark a node as visited before pushing its neighbors to the stack/queue can lead to infinite loops, especially in graphs with cycles.
2. Stack Overflow: In languages with limited stack size (like Java or Python), deep recursion can cause a stack overflow error for very large graphs. Prefer the iterative approach for massive graphs.
3. Graph Representation: Using an Adjacency Matrix instead of an Adjacency List can lead to O(V^2) time complexity if not optimized, whereas DFS is naturally O(V + E).

Summary

DFS is a versatile algorithm that prioritizes depth. It is memory-efficient for deep graphs and is the go-to choice for problems involving topological sorting, cycle detection, and pathfinding where the shortest path is not the primary concern.