Both visit every reachable node in O(V + E), but the order matters — and so does the memory profile.

BFS — breadth-first

Uses a queue. Explores all neighbors at distance d before distance d+1.

Use BFS when:

• You need the shortest path in an unweighted graph (or fewest edges).
• You need level-order: nearest match first, closest neighbor, friends-of-friends at depth k.
• Memory permits storing the frontier (can be wide on dense graphs).

function bfs(start, adj) {
  const visited = new Set([start]);
  const queue = [[start, 0]];
  while (queue.length) {
    const [node, dist] = queue.shift();
    for (const n of adj[node] || []) {
      if (!visited.has(n)) {
        visited.add(n);
        queue.push([n, dist + 1]);
      }
    }
  }
}

(For hot loops, use an index-based or linked-list queue — shift is O(n).)

DFS — depth-first

Uses a stack (or recursion). Dives along one branch before backtracking.

Use DFS when:

• Connectivity / connected components — does a path exist? Who's reachable?
• Cycle detection in directed/undirected graphs.
• Topological sort (DFS post-order on a DAG).
• Path enumeration / backtracking — N-Queens, word search, Sudoku.
• Memory is tight — DFS holds only the current path.

function dfs(node, adj, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  for (const n of adj[node] || []) dfs(n, adj, visited);
}

The decision

Gotchas

• Always track visited — graphs may have cycles.
• Weighted graphs — neither BFS nor plain DFS gives shortest path; use Dijkstra.
• Very deep graphs — recursive DFS can blow the stack; use iterative DFS.

Interview framing

"BFS for shortest path in unweighted graphs and level-order problems — it explores by distance from the source. DFS for connectivity, cycle detection, topological sort, and path enumeration — it's also lighter on memory because you only hold the current path. Both need a visited set. For weighted graphs, neither: you need Dijkstra."