When should you use BFS versus DFS on a graph?

beginner

Re-explain

Use BFS when nearness matters and DFS when the graph's structure matters. Both visit every reachable vertex in O(V + E) time, so the choice is about order and memory, not raw speed. BFS explores by distance, and DFS explores by depth.

BFS finds the fewest-edge path, works well for "closest match" and level-by-level problems, and suits shallow, wide searches. DFS fits cycle detection, connected components and topological sort, where you want to fully explore each branch.

Memory is the other tiebreaker:

BFS holds a whole frontier, which can be huge on wide graphs
DFS holds only the current path, but recursion can overflow on very deep graphs

So if you care about shortest hops, or the answer is likely nearby, use BFS. If you care about the graph's overall shape, use DFS.

Rewriting in plainer words…

This answer doesn't lend itself to a diagram - it reads best . No credits were charged.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·

What should the new diagram focus on?

Guided practice for Graphs One question at a time. Answer out loud, get graded, see what you missed.

How well did you know this?

AI:

Saved in this browser - sign in to keep your review list.

How should your speech become text?

Listening… your words appear above as you speak - tap Stop when you're done.

Recording · cr - tap Stop & transcribe when you're done.

Transcribing with AI…

Voice:

Keep going - a few more words and AI can grade it.

Interview lens How interviewers actually use this question

Likely follow-ups

Once edges carry weights, does BFS still find the shortest path? What would you use instead? BFS counts edges, not total weight. Name Dijkstra for non-negative weights, and 0-1 BFS when every weight is 0 or 1.
Your recursive DFS crashes on a graph that is one long chain. How do you fix it? Replace recursion with an explicit stack on the heap. Note the visit order can change unless you push neighbors in reverse.
You said DFS for topological sort. How would you do it BFS-style, and when would you pick that? Name Kahn's algorithm, which keeps removing nodes with in-degree zero. Any nodes left over mean the graph has a cycle.
In a grid with many exits, how do you find every cell's distance to its nearest exit? Start one BFS with every exit in the queue at distance 0. That is one O(V + E) pass instead of one search per exit.
Is there a way to get BFS's fewest-edge guarantee while using only DFS-sized memory? Name iterative deepening, depth-limited DFS with a growing limit. It redoes shallow levels, which costs little when branching is high.

What you can say

I use BFS when nearness matters and DFS when the graph's structure matters.
Speed doesn't decide it. Both visit every reachable vertex in O(V + E), so the real differences are visit order and memory.
BFS explores by distance, so it finds the fewest-edge path. It fits closest-match and level-by-level problems, and shallow, wide searches.
DFS goes deep and finishes each branch before backing up, which is what cycle detection, connected components and topological sort need.
So if I care about shortest hops or the answer is probably nearby, BFS. If I care about the graph's overall shape, DFS.
Memory breaks ties. BFS holds a whole frontier, which can get huge on wide graphs, and DFS holds only the current path but can overflow the stack on very deep graphs.

Weak answers to avoid

Says one is faster than the other Both run in O(V + E) on the reachable part of the graph. The choice comes down to visit order and memory, so say that.
Uses DFS to find a shortest path The first path DFS finds to a node can be far from the shortest. In an unweighted graph BFS gives the fewest-edge path, so reach for it.
Treats DFS memory as free DFS keeps only the current path, but recursion on a very deep graph can overflow the stack. Mention the explicit-stack fix.
Says BFS finds shortest paths with weights too BFS minimizes edge count, not total weight. Say it holds for unweighted graphs and that weighted ones need something like Dijkstra.

Interview lens

Likely follow-ups, what you can say, and the weak answers to avoid.

Want a quick review of the fundamentals? See the Graphs cheatsheet.

← Back to all Graphs questions

Pro · $10/mo

51 of 60 Graphs answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

Full answers + code
AI explanations, simpler or deeper
1,000 AI credits / month
Cancel anytime

Get Pro → See plans & pricing →