Depth-First Search (DFS): Complete Guide

Master DFS for pathfinding, cycle detection, and backtracking. Covers recursive/iterative implementations, topological sorting, and advanced optimizations with real-world applications.

DFS Usage in Tech (2023)

Pathfinding (30%)

Dependency Resolution (25%)

Cycle Detection (20%)

Backtracking (15%)

Other (10%)

1. DFS Core Concepts

Key Properties:

Depth-First: Explores as far as possible along each branch
LIFO Principle: Uses stack (recursive call stack or explicit)
Backtracking: Natural support for undo operations
Memory Efficient: Space complexity = O(height)

Time Complexities:

Structure	Time	Space
Adjacency List	O(V + E)	O(V)
Adjacency Matrix	O(V²)	O(V)
Binary Tree	O(N)	O(H)
Backtracking	O(bᵈ)	O(d)

Implementation Comparison:

Recursive DFS


function dfs(node, visited = new Set()) {
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited);
    }
  }
}

Pros: Simple, elegant
Cons: Stack overflow risk

Iterative DFS


function dfs(start) {
  const stack = [start];
  const visited = new Set([start]);
  
  while (stack.length) {
    const node = stack.pop();
    for (const neighbor of graph[node].reverse()) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
}

Pros: No stack limits
Cons: Manual reversal for ordering

2. DFS Traversal Types

Pre-Order (Root-Left-Right)


function preOrder(node) {
  if (!node) return;
  console.log(node.val);  // Process first
  preOrder(node.left);
  preOrder(node.right);
}

Use Case: Clone trees, prefix notation

In-Order (Left-Root-Right)


function inOrder(node) {
  if (!node) return;
  inOrder(node.left);
  console.log(node.val);  // Process middle
  inOrder(node.right);
}

Use Case: BST → Sorted array

Post-Order (Left-Right-Root)


function postOrder(node) {
  if (!node) return;
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.val);  // Process last
}

Use Case: Delete trees, reverse polish

Topological Sort (Modified DFS)


function topologicalSort(graph) {
  const stack = [];
  const visited = new Set();
  
  function dfs(node) {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
    stack.push(node);  // Post-order
  }
  
  for (const node in graph) {
    if (!visited.has(node)) dfs(node);
  }
  return stack.reverse();
}

3. Advanced DFS Techniques

Cycle Detection


function hasCycle(graph) {
  const visited = new Set();
  const recStack = new Set();
  
  function dfs(node) {
    if (recStack.has(node)) return true;
    if (visited.has(node)) return false;
    
    visited.add(node);
    recStack.add(node);
    
    for (const neighbor of graph[node]) {
      if (dfs(neighbor)) return true;
    }
    
    recStack.delete(node);
    return false;
  }
  
  for (const node in graph) {
    if (dfs(node)) return true;
  }
  return false;
}

Backtracking Template


function backtrack(path, choices) {
  if (isSolution(path)) {
    output(path);
    return;
  }
  
  for (const choice of choices) {
    if (isValid(choice)) {
      makeChoice(path, choice);
      backtrack(path, nextChoices);
      undoChoice(path, choice);
    }
  }
}

Applications:

Sudoku Solver: Try numbers → backtrack if invalid
N-Queens: Place queens → backtrack on conflict
Maze Solving: Explore paths → backtrack at dead ends
Subsets/Permutations: Build candidates incrementally

DFS Problem Patterns

Problem Type	DFS Approach	Example
Connected Components	Explore all reachable nodes	Number of Islands
Path Finding	Track path in recursion	All Paths in Graph
Tree Operations	Pre/In/Post-order	BST Validation
Backtracking	Try → Undo → Retry	Subsets/Permutations

Expert Tip: DFS shines in problems requiring exhaustive search or path exploration. For shortest path in unweighted graphs, prefer BFS. Combine DFS with memoization for dynamic programming problems.

0 Interaction

0 Views

0 Likes