Graph Traversal — BFS vs DFS, Traced (and when to use which)
BFS and DFS: the two ways to visit a graph
Both visit every reachable node once (O(V+E)); they differ in order, and the order is what makes each suited to different problems. BFS spreads out level by level (a queue); DFS plunges deep then backtracks (a stack / recursion).
The two templates
// BFS — shortest path in an UNWEIGHTED graph, level order
Queue<Node> q = new ArrayDeque<>(); q.add(start);
Set<Node> seen = new HashSet<>(); seen.add(start); // mark on ENQUEUE, not dequeue
while (!q.isEmpty()) {
Node u = q.poll();
for (Node v : adj(u)) if (seen.add(v)) q.add(v);
}
// DFS — recursive (paths, cycles, topological sort)
void dfs(Node u, Set<Node> seen) {
seen.add(u);
for (Node v : adj(u)) if (!seen.contains(v)) dfs(v, seen);
}Which one, when
| BFS | DFS | |
|---|---|---|
| Structure | queue, level by level | stack/recursion, deep first |
| Use for | shortest path (unweighted), level/min-steps | paths, cycle detection, topological sort, connected components |
| Memory | O(width) — can be large | O(depth) — the call stack |
Graph pattern family to recognise: shortest-unweighted → BFS · topo order / cycle → DFS (3-colour) or Kahn's (BFS indegree) · connectivity/islands → either + visited · weighted shortest → Dijkstra (a BFS with a priority queue).
Pitfalls
- Forgetting
visited→ infinite loop on any cycle. Mark BFS nodes on enqueue (not dequeue) or they get added twice. - Deep recursion → stack overflow; convert DFS to an explicit stack for huge graphs.
- Disconnected graph: loop over all nodes as start points to cover every component.
Takeaways
- Both O(V+E); BFS = queue/levels/shortest-unweighted, DFS = stack/deep/cycles/topo.
- Always track
visited; mark BFS on enqueue. - Most graph problems are a labelled variant of these two.
Re-authored for this guide; traversal diagram hand-authored as SVG. See also: Graphs, Trees, the Pattern Recognition index.
🤖 Don't fully get this? Learn it with Claude
Stuck on Graph Traversal — BFS vs DFS, Traced (and when to use which)? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Graph Traversal — BFS vs DFS, Traced (and when to use which)** (DSA) and want to truly understand it. Explain Graph Traversal — BFS vs DFS, Traced (and when to use which) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **Graph Traversal — BFS vs DFS, Traced (and when to use which)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **Graph Traversal — BFS vs DFS, Traced (and when to use which)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **Graph Traversal — BFS vs DFS, Traced (and when to use which)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.