Kata: Depth-First Search

Table of contents

Problem Statement

Implement depth-first search on a graph to solve:

1. Path finding: Find a path from start to end (return the path, not just boolean)
2. All paths: Find all possible paths between two vertices
3. Cycle detection: Detect if the graph contains a cycle

Use the graph representation from Kata: Graph Traversal.

Concepts

DFS explores as deep as possible along each branch before backtracking. It uses a stack (explicit or via recursion).

Applications: topological sort, cycle detection, maze solving, connected components, path finding.

DFS vs BFS: DFS finds a path (not necessarily shortest). BFS finds the shortest path in unweighted graphs.

TypeScript: Uses Map and Set for adjacency lists and visited tracking. See TypeScript Core Concepts.

Python: Generators make DFS particularly elegant. See Python Core Concepts.

Boilerplate

TypeScript

// dfs.ts
type Graph = Map<string, string[]>;

function findPath(
  graph: Graph,
  start: string,
  end: string
): string[] | null {
  // TODO: return path or null
  return null;
}

function findAllPaths(
  graph: Graph,
  start: string,
  end: string
): string[][] {
  // TODO: return all possible paths
  return [];
}

function hasCycle(graph: Graph): boolean {
  // TODO: detect cycle in directed graph
  return false;
}

Hints

Solution

TypeScript

type Graph = Map<string, string[]>;

function findPath(
  graph: Graph,
  start: string,
  end: string
): string[] | null {
  const visited = new Set<string>();

  function dfs(current: string, path: string[]): string[] | null {
    if (current === end) return [...path, current];

    visited.add(current);

    for (const neighbor of graph.get(current) ?? []) {
      if (!visited.has(neighbor)) {
        const result = dfs(neighbor, [...path, current]);
        if (result) return result;
      }
    }

    return null;
  }

  return dfs(start, []);
}

function findAllPaths(
  graph: Graph,
  start: string,
  end: string
): string[][] {
  const paths: string[][] = [];

  function dfs(current: string, path: string[]): void {
    if (current === end) {
      paths.push([...path, current]);
      return;
    }

    for (const neighbor of graph.get(current) ?? []) {
      if (!path.includes(neighbor)) {
        dfs(neighbor, [...path, current]);
      }
    }
  }

  dfs(start, []);
  return paths;
}

function hasCycle(graph: Graph): boolean {
  const WHITE = 0; // unvisited
  const GRAY = 1; // in progress
  const BLACK = 2; // completed

  const color = new Map<string, number>();
  for (const vertex of graph.keys()) {
    color.set(vertex, WHITE);
  }

  function dfs(vertex: string): boolean {
    color.set(vertex, GRAY);

    for (const neighbor of graph.get(vertex) ?? []) {
      if (color.get(neighbor) === GRAY) return true; // back edge = cycle
      if (color.get(neighbor) === WHITE && dfs(neighbor)) return true;
    }

    color.set(vertex, BLACK);
    return false;
  }

  for (const vertex of graph.keys()) {
    if (color.get(vertex) === WHITE && dfs(vertex)) {
      return true;
    }
  }

  return false;
}

Python

from collections import defaultdict

Graph = defaultdict[str, list[str]]

def find_path(graph: Graph, start: str, end: str) -> list[str] | None:
    visited: set[str] = set()

    def dfs(current: str, path: list[str]) -> list[str] | None:
        if current == end:
            return path + [current]

        visited.add(current)

        for neighbor in graph[current]:
            if neighbor not in visited:
                result = dfs(neighbor, path + [current])
                if result is not None:
                    return result

        return None

    return dfs(start, [])

def find_all_paths(graph: Graph, start: str, end: str) -> list[list[str]]:
    paths: list[list[str]] = []

    def dfs(current: str, path: list[str]) -> None:
        if current == end:
            paths.append(path + [current])
            return

        for neighbor in graph[current]:
            if neighbor not in path:
                dfs(neighbor, path + [current])

    dfs(start, [])
    return paths

def has_cycle(graph: Graph) -> bool:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph}

    def dfs(vertex: str) -> bool:
        color[vertex] = GRAY
        for neighbor in graph[vertex]:
            if color.get(neighbor) == GRAY:
                return True
            if color.get(neighbor, WHITE) == WHITE and dfs(neighbor):
                return True
        color[vertex] = BLACK
        return False

    return any(
        dfs(v) for v in graph if color[v] == WHITE
    )

Complexity Analysis

Finding all paths is exponential in the worst case (complete graph), but typically feasible for sparse graphs.

Cross-Language Notes

Python: Python has a default recursion limit of 1000. For deep graphs, use sys.setrecursionlimit() or convert to iterative DFS with an explicit stack.

PHP: PHP also has a recursion limit tied to xdebug.max_nesting_level (default 256 with Xdebug). Use iterative DFS for production code.

Functional languages: In Haskell or OCaml, DFS is naturally expressed as a fold over the graph structure, with pattern matching for base cases.

See also: Kata: Graph Traversal for basic BFS/DFS, and Kata: Dijkstra’s Shortest Path for weighted shortest paths.