Depth-First Search

What is DFS?

Depth-First Search (DFS) is a graph/tree traversal algorithm that explores as far down a branch as possible before backtracking. It uses a stack (or recursion) to track which nodes to visit next.

Key Idea: Go DEEP first — follow one path all the way to the end, then backtrack.

How It Works

Algorithm (recursive):
  1. Start at the root/source node, mark it as visited
  2. Process current node
  3. For each unvisited neighbor:
     a. Recursively visit it (go deeper)
  4. Backtrack when no unvisited neighbors remain

Algorithm (iterative):
  1. Push source node onto the stack
  2. While stack is not empty:
     a. Pop the top node (current)
     b. If not visited: mark as visited, process it
     c. Push all unvisited neighbors onto the stack
  3. Repeat until stack is empty

Data structure: Stack (LIFO — last in, first out) or call stack (recursion)

Visualization

Graph:
        A
       / \
      B   C
     / \   \
    D   E   F

DFS from A (goes deep before wide):

  Visit A → go to B
  Visit B → go to D
  Visit D → no unvisited neighbors → backtrack
  Back at B → go to E
  Visit E → no unvisited neighbors → backtrack
  Back at A → go to C
  Visit C → go to F
  Visit F → no unvisited neighbors → done

Traversal order: A → B → D → E → C → F

Compare to BFS (visits level by level):
  BFS order:  A → B → C → D → E → F
  DFS order:  A → B → D → E → C → F  ✓ branch by branch

Time & Space Complexity

Time Complexity:   O(V + E)
  - V = number of vertices (nodes)
  - E = number of edges
  - Each node and edge is visited at most once

Space Complexity:  O(V)
  - Recursive: O(depth) call stack — O(V) worst case (linear graph)
  - Iterative: O(V) explicit stack in worst case

DFS properties:
  ✓ Memory-efficient for deep, narrow graphs (O(depth) vs BFS O(width))
  ✓ Simple to implement recursively
  ✓ Natural fit for cycle detection and topological sort
  ✗ Does NOT guarantee shortest path
  ✗ Can get stuck in deep branches (iterative preferred for very deep graphs)

When to Use DFS

Use DFS when:
  ✓ Detecting cycles in a graph
  ✓ Topological sorting (DAGs)
  ✓ Finding connected / strongly connected components
  ✓ Solving mazes and puzzles (path existence)
  ✓ Tree traversals (pre-order, in-order, post-order)
  ✓ Generating permutations / combinations (backtracking)
  ✓ Memory is constrained (DFS uses O(depth) vs BFS O(width))

Use BFS instead when:
  ✗ You need the shortest path (fewest hops)
  ✗ Graph is wide and shallow (DFS memory = BFS memory here)
  ✗ Finding nearest neighbor or closest node

Use Dijkstra instead when:
  ✗ Graph has weighted edges and you need shortest path by weight

TypeScript Implementation

// DFS on a graph (adjacency list) — recursive
function dfsRecursive(
  graph: Map<string, string[]>,
  start: string,
  visited = new Set<string>(),
  order: string[] = []
): string[] {
  visited.add(start);
  order.push(start);

  for (const neighbor of graph.get(start) ?? []) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited, order); // Go deeper
    }
  }

  return order;
}

// DFS on a graph — iterative (avoids call stack overflow on deep graphs)
function dfsIterative(graph: Map<string, string[]>, start: string): string[] {
  const visited = new Set<string>();
  const stack: string[] = [start]; // LIFO stack
  const order: string[] = [];

  while (stack.length > 0) {
    const current = stack.pop()!; // Pop from top

    if (visited.has(current)) continue;
    visited.add(current);
    order.push(current);

    // Push neighbors in reverse so left-to-right order is preserved
    const neighbors = graph.get(current) ?? [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
      }
    }
  }

  return order;
}

// Cycle detection in a directed graph using DFS
function hasCycle(graph: Map<string, string[]>): boolean {
  const visited = new Set<string>();
  const inStack = new Set<string>(); // Nodes in current recursion path

  function dfs(node: string): boolean {
    visited.add(node);
    inStack.add(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor) && dfs(neighbor)) return true;
      if (inStack.has(neighbor)) return true; // Back edge = cycle
    }

    inStack.delete(node); // Remove from path on backtrack
    return false;
  }

  for (const node of graph.keys()) {
    if (!visited.has(node) && dfs(node)) return true;
  }

  return false;
}

// Topological sort (DFS post-order on a DAG)
function topologicalSort(graph: Map<string, string[]>): string[] {
  const visited = new Set<string>();
  const result: string[] = [];

  function dfs(node: string): void {
    visited.add(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }

    result.push(node); // Add AFTER visiting all descendants (post-order)
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) dfs(node);
  }

  return result.reverse(); // Reverse post-order = topological order
}

// Usage
const graph = new Map<string, string[]>([
  ['A', ['B', 'C']],
  ['B', ['A', 'D', 'E']],
  ['C', ['A', 'F']],
  ['D', ['B']],
  ['E', ['B']],
  ['F', ['C']],
]);

console.log(dfsRecursive(graph, 'A'));
// → ['A', 'B', 'D', 'E', 'C', 'F']

console.log(dfsIterative(graph, 'A'));
// → ['A', 'B', 'D', 'E', 'C', 'F']

Python Implementation

from collections import defaultdict

def dfs_recursive(
    graph: dict[str, list[str]],
    start: str,
    visited: set | None = None,
    order: list | None = None
) -> list[str]:
    """Traverse graph using DFS recursively, return visit order."""
    if visited is None:
        visited = set()
    if order is None:
        order = []

    visited.add(start)
    order.append(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)  # Go deeper

    return order


def dfs_iterative(graph: dict[str, list[str]], start: str) -> list[str]:
    """Traverse graph using DFS iteratively (avoids recursion limit)."""
    visited = set()
    stack = [start]     # LIFO stack
    order = []

    while stack:
        current = stack.pop()   # Pop from top

        if current in visited:
            continue
        visited.add(current)
        order.append(current)

        # Push neighbors in reverse to preserve left-to-right order
        for neighbor in reversed(graph[current]):
            if neighbor not in visited:
                stack.append(neighbor)

    return order


def has_cycle_directed(graph: dict[str, list[str]]) -> bool:
    """Detect cycle in a directed graph using DFS."""
    visited = set()
    in_stack = set()    # Nodes in the current recursion path

    def dfs(node: str) -> bool:
        visited.add(node)
        in_stack.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited and dfs(neighbor):
                return True
            if neighbor in in_stack:    # Back edge = cycle
                return True

        in_stack.remove(node)   # Backtrack
        return False

    return any(dfs(node) for node in graph if node not in visited)


def topological_sort(graph: dict[str, list[str]]) -> list[str]:
    """Topological sort of a DAG using DFS post-order."""
    visited = set()
    result = []

    def dfs(node: str) -> None:
        visited.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

        result.append(node)     # Add AFTER all descendants are visited

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

    return result[::-1]         # Reverse post-order = topological order


def dfs_find_all_paths(
    graph: dict[str, list[str]], start: str, end: str
) -> list[list[str]]:
    """Find ALL paths from start to end using DFS backtracking."""
    all_paths = []

    def dfs(current: str, path: list[str], visited: set) -> None:
        if current == end:
            all_paths.append(list(path))    # Found a complete path
            return

        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                path.append(neighbor)
                dfs(neighbor, path, visited)    # Recurse
                path.pop()                      # Backtrack
                visited.remove(neighbor)

    dfs(start, [start], {start})
    return all_paths


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

print(dfs_recursive(graph, 'A'))
# → ['A', 'B', 'D', 'E', 'C', 'F']

print(dfs_iterative(graph, 'A'))
# → ['A', 'B', 'D', 'E', 'C', 'F']

print(dfs_find_all_paths(graph, 'A', 'F'))
# → [['A', 'C', 'F']]

DFS vs BFS

Rule of thumb:
  → "Does a path exist?"       →  DFS
  → "Shortest / fewest steps"  →  BFS
  → "Weighted shortest path"   →  Dijkstra