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).

Step-by-step trace on the same graph

Assume the graph above: A is connected to B and C; B is connected to D; C is connected to E. Neighbours are visited in alphabetical order.

BFS — queue state, level by level

step	dequeue	queue after enqueue	visited
1	A	[B, C]	A, B, C
2	B	[C, D]	A, B, C, D
3	C	[D, E]	A, B, C, D, E
4	D	[E]	A, B, C, D, E
5	E	[]	A, B, C, D, E

Order visited: A, B, C, D, E — shortest path from A to any node is found first. The reason is the FIFO queue: it drains one whole distance-layer before any vertex of the next, so BFS dequeues vertices in non-decreasing distance order, and the first time a node is discovered its hop-count from the source is already minimal.

DFS — recursion stack, deep then backtrack

step	call	action
1	dfs(A)	visit A; recurse on first unvisited neighbour B
2	dfs(B)	visit B; recurse on first unvisited neighbour D
3	dfs(D)	visit D; no unvisited neighbours → return to B
4	dfs(B)	no more neighbours → return to A
5	dfs(A)	next unvisited neighbour is C → recurse
6	dfs(C)	visit C; recurse on first unvisited neighbour E
7	dfs(E)	visit E; no unvisited neighbours → return

Order visited: A, B, D, C, E — goes as deep as possible before backtracking.

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.

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.

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.

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.

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.