Algorithmseasy

BFS vs DFS — what’s the difference and when to use which?

Answer

BFS explores level by level and finds the shortest path in an unweighted graph. DFS goes deep first and is handy for traversals, cycle detection, and topological-style problems.

function bfs(start: number, graph: number[][]) {
  const q: number[] = [start];
  const seen = new Set<number>([start]);

  while (q.length) {
    const v = q.shift()!;
    for (const n of graph[v]) {
      if (!seen.has(n)) {
        seen.add(n);
        q.push(n);
      }
    }
  }
}

Advanced answer

Deep dive

Both algorithms visit each vertex/edge at most a constant number of times, so the baseline time is O(V+E). The difference is order and the data structure.

BFS uses a queue and explores in increasing distance (layers). That’s why it gives shortest paths in unweighted graphs.
DFS uses a stack (often recursion) and explores as deep as possible; it’s great for entry/exit ordering.

When to use which

BFS: shortest path by number of edges, level order, bipartite check, minimum moves.
DFS: cycle detection (directed graphs), topological reasoning, connected components, backtracking.

Practical notes

In JS, `shift()` makes BFS slow; prefer an index-based queue.
DFS recursion can overflow on deep graphs; use an explicit stack when needed.

Answer

Advanced answer

Deep dive

When to use which

Practical notes

Related questions