Depth-First Search

graphrecursivebacktracking

Press play to start

1function dfs(graph: Record<string, string[]>, start: string): string[] {
const visited = new Set<string>();
const stack = [start];
const order: string[] = [];
while (stack.length > 0) {
  const node = stack.pop()!;
  if (visited.has(node)) continue;
  visited.add(node);
  order.push(node);
  for (const nb of (graph[node] ?? []).slice().reverse()) {
    if (!visited.has(nb)) stack.push(nb);
  }
}
return order;
15}

Step 1/0

Complexity

Best:O(V+E)
Average:O(V+E)
Worst:O(V+E)
Space:O(V)

Description

Explores as far as possible along each branch before backtracking. Uses a stack (or recursion) to track nodes to visit.

When to use

Cycle detection, topological sort, path finding, maze solving. Memory-efficient for deep graphs compared to BFS.