name: DFS (Depth-First Search)
slug: dfs
difficulty_level: 3
pattern_type: algorithm
display_order: 7

description: >
  Explore as deep as possible along each branch before backtracking, using
  recursion or an explicit stack. DFS is memory-efficient and naturally suited
  for problems involving paths, connectivity, and exhaustive exploration.

when_to_use: |
  - Finding any path (not necessarily shortest)
  - Detecting cycles in graphs
  - Topological sorting
  - Connected components
  - Tree traversals (preorder, inorder, postorder)
  - Exhaustive search when you need to explore all possibilities

metaphor: |
  Imagine exploring a maze by always taking the first available turn until you
  hit a dead end. Then you backtrack to the last intersection and try the next
  option. You keep going deeper until stuck, then retreat and try alternatives.

  Another analogy: reading a "choose your own adventure" book. You follow one
  story path all the way to its ending, then go back and explore different
  choices you didn't take.

core_concept: |
  DFS uses a **stack** (LIFO)—either the call stack via recursion or an explicit
  stack data structure. This naturally explores depth-first: the most recently
  discovered node is explored first.

  The key insight is that DFS maintains the current path from root to current
  node on the stack. This makes it perfect for:

  1. **Path problems**: The current path is always available during recursion
  2. **Cycle detection**: If you encounter a node already on the current path,
     there's a cycle
  3. **Backtracking**: Naturally undo choices when returning from recursion

  Unlike BFS, DFS doesn't guarantee shortest paths, but it uses O(h) memory
  (height of tree/recursion depth) vs BFS's O(w) (width of level).

visualization: |
  **Example: DFS traversal of graph**

  ```
  Graph:
      A --- B --- E
      |     |
      C --- D --- F

  DFS from A (alphabetical order):

  Visit A → explore neighbors
    Visit B → explore neighbors
      Visit D → explore neighbors
        Visit C (already visited? skip or detect cycle)
        Visit F → no unvisited neighbors, backtrack
      Backtrack to D, backtrack to B
      Visit E → no unvisited neighbors, backtrack
    Backtrack to B, backtrack to A
    Visit C → D already visited, backtrack
  Done

  Order visited: A → B → D → F → E → C
  ```

  **Recursion call stack visualisation:**

  ```
  dfs(A)
    └─ dfs(B)
         └─ dfs(D)
              └─ dfs(F) ← returns
              └─ dfs(C) ← already visited
         └─ dfs(E) ← returns
    └─ dfs(C) ← already visited
  ```

  **Cycle detection with colors:**

  ```
  WHITE (0) = unvisited
  GRAY  (1) = in current path (on stack)
  BLACK (2) = fully processed

  If we visit a GRAY node → cycle detected!
  ```

code_template: |
  def dfs_recursive(graph: dict, start: str, visited: set = None) -> list:
      """Basic recursive DFS traversal."""
      if visited is None:
          visited = set()

      visited.add(start)
      result = [start]

      for neighbor in graph[start]:
          if neighbor not in visited:
              result.extend(dfs_recursive(graph, neighbor, visited))

      return result


  def dfs_iterative(graph: dict, start: str) -> list:
      """Iterative DFS using explicit stack."""
      visited = set()
      stack = [start]
      result = []

      while stack:
          node = stack.pop()
          if node in visited:
              continue

          visited.add(node)
          result.append(node)

          # Add neighbors in reverse for same order as recursive
          for neighbor in reversed(graph[node]):
              if neighbor not in visited:
                  stack.append(neighbor)

      return result


  def dfs_path_finding(graph: dict, start: str, end: str) -> list:
      """Find a path from start to end using DFS."""
      def dfs(node: str, path: list) -> list:
          if node == end:
              return path

          for neighbor in graph[node]:
              if neighbor not in path:  # Avoid cycles
                  result = dfs(neighbor, path + [neighbor])
                  if result:
                      return result

          return []

      return dfs(start, [start])


  def detect_cycle(graph: dict) -> bool:
      """Detect cycle in directed graph using DFS."""
      WHITE, GRAY, BLACK = 0, 1, 2
      color = {node: WHITE for node in graph}

      def dfs(node: str) -> bool:
          color[node] = GRAY  # Mark as being processed

          for neighbor in graph[node]:
              if color[neighbor] == GRAY:  # Back edge = cycle
                  return True
              if color[neighbor] == WHITE and dfs(neighbor):
                  return True

          color[node] = BLACK  # Mark as complete
          return False

      return any(color[node] == WHITE and dfs(node) for node in graph)


  def topological_sort(graph: dict) -> list:
      """Topological sort using DFS (Kahn's algorithm alternative)."""
      visited = set()
      result = []

      def dfs(node: str):
          visited.add(node)
          for neighbor in graph.get(node, []):
              if neighbor not in visited:
                  dfs(neighbor)
          result.append(node)  # Add after all descendants

      for node in graph:
          if node not in visited:
              dfs(node)

      return result[::-1]  # Reverse for topological order

recognition_signals:
  - "find path"
  - "detect cycle"
  - "connected components"
  - "topological sort"
  - "all paths"
  - "explore all"
  - "tree traversal"
  - "preorder"
  - "postorder"
  - "inorder"
  - "number of islands"
  - "flood fill"

common_mistakes:
  - title: Stack overflow with deep recursion
    description: |
      Recursive DFS on large graphs or trees can exceed Python's default
      recursion limit (usually 1000), causing a stack overflow.
    fix: |
      Either increase the limit with `sys.setrecursionlimit(10000)` or convert
      to iterative DFS with an explicit stack. Iterative is safer for unknown
      input sizes.

  - title: Marking visited too late
    description: |
      In iterative DFS, checking visited only when popping (not when pushing)
      allows the same node to be added multiple times, wasting memory.
    fix: |
      For iterative DFS, either check when popping (simpler but less efficient)
      or mark visited when pushing (more efficient):
      ```python
      if neighbor not in visited:
          visited.add(neighbor)  # Mark when adding
          stack.append(neighbor)
      ```

  - title: Confusing visited vs current path
    description: |
      For cycle detection in directed graphs, using a simple visited set doesn't
      distinguish between "node in current path" (cycle) and "node fully processed"
      (not a cycle, just already explored).
    fix: |
      Use three states (WHITE/GRAY/BLACK) or track the current path separately.
      A cycle exists only if you revisit a node that's still on the current path.

  - title: Wrong order in topological sort
    description: |
      Adding nodes to result before processing descendants gives reverse
      topological order or incorrect order entirely.
    fix: |
      Add nodes to result only after all descendants are processed (post-order).
      Then reverse the result at the end.

variations:
  - name: Tree DFS (preorder/inorder/postorder)
    description: |
      Visit nodes in specific orders relative to processing children. Preorder
      visits parent first, inorder visits between children, postorder visits
      parent last.
    example: "Binary Tree Inorder Traversal, Serialize/Deserialize BST"

  - name: Graph DFS
    description: |
      Traverse all reachable nodes from a starting point. Need to track visited
      nodes to avoid infinite loops in cyclic graphs.
    example: "Number of Islands, Clone Graph, Course Schedule"

  - name: DFS with backtracking
    description: |
      Explore paths and undo choices when they don't lead to a solution. The
      natural call stack provides the backtracking mechanism.
    example: "N-Queens, Sudoku Solver, Permutations"

  - name: DFS with memoization
    description: |
      Cache results of DFS from each node to avoid recomputation. Transforms
      DFS into dynamic programming for certain problems.
    example: "Longest Increasing Path in Matrix, Word Break"

  - name: Iterative deepening DFS
    description: |
      Run DFS with increasing depth limits. Combines BFS's shortest-path
      guarantee with DFS's memory efficiency.
    example: "Finding shortest path when memory is limited"

related_patterns:
  - bfs
  - backtracking
  - tree-traversal
  - matrix-traversal

prerequisite_patterns: []
