BFS or DFS: which one to use

Graphs Junior Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

Which question calls for BFS rather than DFS?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A The fewest moves for a knight between two squares

Right: every move costs the same, so layer order gives the minimum.

Equal-cost moves plus a 'fewest' question is the signal for breadth-first search.

Why not the others?
  • B Whether a dependency graph has a loop. That is a DFS job with three states.
  • C Listing every subset of a set. That is backtracking, a form of DFS.

30-second answer

Both visit every reachable node in O(V + E). BFS explores in layers with a queue, so it finds the fewest edges to any node and suits 'shortest' and 'nearest' questions. DFS goes deep with a stack (or recursion), which suits connectivity, cycle detection, topological order and backtracking. Memory differs: BFS holds a whole layer, DFS holds one path.

Practise saying it · 45 s. No recording, just a timer

Compare BFS and DFS.

Say your answer out loud, then check which of these points you covered:

  • Both O(V + E)
  • BFS: shortest in unweighted graphs
  • DFS: cycles, order, backtracking

Deep dive

Either works for counting connected pieces; pick the one you write fastest.

DFS recursion depth can reach V; switch to an explicit stack on large inputs.

BFS with a deque is the default for unweighted shortest paths; weighted needs Dijkstra.

Common mistakes

  • Using DFS to find a shortest path in an unweighted graph.
  • Popping from the front of a Python list for BFS.

Senior take & follow-ups

Tie the choice to the question's wording: 'fewest' or 'nearest' means BFS.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is iterative deepening?

    Show hint

    Repeated depth-limited DFS: BFS's shortest-path guarantee with DFS's memory.

  2. Which one finds a topological order?

    Show hint

    DFS post-order reversed, or Kahn's BFS-style algorithm.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

Try it in a free tool

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.