BFS vs DFS -- When to Use Which

Quick Revisit

• Reach for this when you have a graph traversal problem and need to pick BFS or DFS.
• The decision rule: distance info -> BFS; structural info (cycles, bridges, SCC, entry/exit times) -> DFS; just reachability -> either, DFS is usually shorter.
• DFS does NOT find shortest paths. Recursive DFS stack-overflows on large graphs (n > 10^5) in C++ unless you switch to an explicit stack or raise the stack limit. Both are easy traps to fall into.
• See also: DP vs Greedy Guide, Graph Modeling.

Quick decision guide for graph traversal strategy.

---

Contents

• The One-Minute Decision Tree
• Side-by-Side Comparison
• When BFS is the Right Choice
• When DFS is the Right Choice
• Common Mistakes
• Insight Gaps
• Hybrid Approaches
• Self-Test
• What Would You Do If...?
• The Mistake That Teaches
• Cross-References
• Recap

---

+------------------------------------------------------------+ | WARNING: DFS does NOT find shortest paths. If you need | | the shortest path (minimum edges) from A to B in an | | unweighted graph, you MUST use BFS. DFS finds A path, | | not THE shortest path. This is the #1 wrong approach at | | CF 1100-1300. | +------------------------------------------------------------+

BFS on weighted graphs also fails. BFS finds the path with fewest EDGES, not fewest total WEIGHT. For weighted shortest paths, use Dijkstra (non-negative weights) or Bellman-Ford (negative weights).

Exception: 0-1 BFS works when edge weights are only 0 or 1. Use a deque: push weight-0 neighbors to front, weight-1 to back. This is NOT "just BFS with a deque" -- the correctness argument is different (it maintains the invariant that the deque is sorted by distance).

---

The One-Minute Decision Tree

Do you need SHORTEST PATH (unweighted)?
  |
  +-- YES  -->  BFS  (layer-by-layer guarantees minimum edges)
  |
  +-- NO   -->  Do you need to explore ALL paths / detect cycles / backtrack?
                  |
                  +-- YES  -->  DFS  (natural recursion, backtracking)
                  |
                  +-- NO   -->  Either works. DFS is usually simpler to code.

---

Side-by-Side Comparison

Aspect	BFS	DFS
Traversal order	Level by level (breadth-first)	As deep as possible, then backtrack
Data structure	Queue (deque)	Stack (explicit or call stack)
Shortest path	Yes (unweighted graphs)	No guarantee
Space	$O(V)$ -- can be $O(\text{width})$ of the graph	$O(V)$ -- can be $O(\text{depth})$ of the graph
Cycle detection	Possible but awkward	Natural (back edges)
Topological sort	Kahn's algorithm (BFS-based)	DFS-based (reverse post-order)
Connected components	Works	Works
Bridges / articulation	Not standard	Tarjan's algorithm (DFS-based)
SCC	Not standard	Tarjan's or Kosaraju's (DFS-based)
Tree diameter	Two BFS calls	DFS works too

---

When BFS is the Right Choice

1. "Minimum number of moves/steps" -- BFS explores all states at distance $k$ before any at distance $k+1$.
2. "Shortest path in an unweighted graph" -- by definition.
3. 0-1 BFS -- edges have weight 0 or 1. Use a deque: push weight-0 edges to front, weight-1 to back.
4. Multi-source BFS -- start from multiple sources simultaneously (e.g., "distance from nearest fire station to every cell").
5. Level-order traversal -- process all nodes at the same depth together.

---

When DFS is the Right Choice

1. "Find any path" / "does a path exist?" -- DFS finds it faster with less memory.
2. Cycle detection -- a back edge in DFS means a cycle.
3. Topological sort -- DFS post-order (reversed) is the standard approach.
4. Bridges and articulation points -- Tarjan's algorithm requires DFS.
5. Strongly connected components -- both Tarjan's and Kosaraju's are DFS-based.
6. Tree DP -- DFS post-order is the natural evaluation order.
7. Backtracking / exhaustive search -- DFS is the recursion pattern.
8. Euler tour / entry-exit times -- computed during DFS.

---

Quick Decision Table -- 0-1 BFS vs Dijkstra and Iterative vs Recursive DFS

When to Use 0-1 BFS vs Dijkstra

Scenario	Use	Time	Why
All edges weight 0 or 1	0-1 BFS (deque)	O(V + E)	Deque maintains sorted-by-distance invariant without heap overhead
All edges weight 1 (unweighted)	Standard BFS (queue)	O(V + E)	Even simpler -- no need for deque logic
Edges have small integer weights (0..k)	Dial's algorithm or Dijkstra	O(V*k + E)	0-1 BFS only works for {0,1}; for small k, Dial's can help
Arbitrary non-negative weights	Dijkstra (binary heap)	O((V+E) log V)	General-purpose; 0-1 BFS doesn't apply
Negative edge weights	Bellman-Ford / SPFA	O(V*E)	Neither BFS nor Dijkstra handles negative weights correctly

Key insight: 0-1 BFS is not "BFS with a deque" -- it has a different correctness argument. The deque maintains elements sorted by distance (weight-0 edges go to front, weight-1 go to back). Treating it as regular BFS leads to bugs.

  Decision: shortest path algorithm?
  |
  +-- All edges unweighted (weight 1)?
  |   +-- Standard BFS  O(V+E)
  |
  +-- Edge weights in {0, 1}?
  |   +-- 0-1 BFS (deque)  O(V+E)
  |
  +-- Non-negative weights?
  |   +-- Dijkstra (binary heap)  O((V+E) log V)
  |
  +-- Negative weights possible?
      +-- Bellman-Ford  O(V*E)

When Iterative DFS is Mandatory vs Recursive

Scenario	Use Recursive DFS	Use Iterative DFS
n <= 10^4 (small graph)	Yes	Yes (either works)
n > 10^5 (large graph)	No (stack overflow)	Yes (mandatory)
Tree DP / backtracking with state	Yes (natural fit)	Possible but awkward
Bridges / Tarjan's SCC	Yes (standard formulation)	Possible but tricky to get entry/exit times right
Simple reachability / connected components	Yes if n is small	Yes (prefer for safety)
Online judge with 64 KB stack limit	No	Yes (mandatory)

Rules of thumb:

1. Default to iterative DFS on competitive programming problems where n can reach 10^5-10^6. The default stack size (1-8 MB) can't handle 10^5+ recursive calls.
2. Use recursive DFS when the algorithm is naturally recursive (tree DP, backtracking) AND n is safely small (<= 10^4), or when the platform allows increasing stack size.
3. Iterative DFS reverses neighbor order (LIFO). This doesn't matter for reachability/components, but matters for algorithms that compare DFS trees (bridges, SCC). Fix by pushing neighbors in reverse order.

---

Common Mistakes

Mistake	Consequence	Fix
Using DFS for shortest path	Wrong answer -- DFS may find a longer path first	Use BFS
BFS without marking on push	Same node enters queue multiple times -> $O(E)$ memory, TLE	Mark visited when pushing, not when popping
Recursive DFS on large graph	Stack overflow ($n>{10}^5$)	Use iterative DFS with explicit stack
Forgetting to handle disconnected components	Miss nodes in separate components	Loop over all nodes, start BFS/DFS from each unvisited

---

Mental Traps

Integrated from reflection notes

Trap: "DFS is better for trees, BFS is better for general graphs."

Both work on both. The choice depends on what you need from the traversal, not the graph type:

  "Which traversal for which graph?"
  
       Trees          General Graphs
         |                  |
    +----+----+        +----+----+
    |         |        |         |
   DFS      BFS      DFS      BFS
   (both    (both    (both    (both
   work)    work)    work)    work)
    |         |        |         |
    v         v        v         v
  Choose by OPERATION needed, not graph type:
  
  Shortest path?  -------> BFS
  Cycles/topo?    -------> DFS
  Components?     -------> Either (DFS simpler)
  Entry/exit?     -------> DFS

Trap: "BFS and DFS are simple -- I don't need to think about them carefully."

At higher ratings, bugs come from misapplying basics to complex graph models (e.g., a multi-layer graph where the "node" is actually (position, state)). Proper visited marking and correct termination require careful thought.

Trap: "0-1 BFS is just BFS with extra steps."

0-1 BFS uses a deque and has a different correctness argument:

  Standard BFS:                 0-1 BFS:
  +-------+                     +-------+-------+
  | queue | <-- push back       | deque |       |
  +-------+                     +---+---+---+---+
  All edges weight 1            | 0-edges:      |
  FIFO guarantees layers        | push FRONT    |
                                +---------------+
                                | 1-edges:      |
                                | push BACK     |
                                +---------------+
                                Maintains sorted-by-distance invariant

Treating it as "slightly modified BFS" leads to incorrect implementations. The invariant is different: the deque is always sorted by distance.

Trap: "Multi-source BFS is just running BFS from each source separately."

Running $k$ separate BFS calls costs $O(k(V+E))$. Multi-source BFS enqueues all sources at distance 0 and runs a single $O(V+E)$ pass:

  WRONG: k separate passes              RIGHT: one multi-source pass

  for each source s:                     queue <- [all k sources]
    BFS(s) -> dist_s[]                    dist[s] = 0 for every source s
  ans[v] = min over all s               standard BFS from here

  Time: O(k * (V+E))                    Time: O(V + E)

  +-----------------------------------------------+
  | Why it works: BFS explores in distance order.  |
  | The first time cell v is reached, it came from |
  | the nearest source -- because all sources      |
  | started at distance 0 simultaneously.          |
  +-----------------------------------------------+

Trap: "Iterative DFS visits neighbors in the same order as recursive DFS."

Pushing all neighbors onto a stack reverses the visit order (LIFO):

  Recursive DFS on adj[A] = [B, C, D]:

    visit(A)
      visit(B)  <- first neighbor visited FIRST
        ...
      visit(C)
      visit(D)

  Naive iterative DFS (push B, C, D):

    stack: [A]
    pop A -> push B, C, D
    stack: [B, C, D]
    pop D  <- last neighbor visited FIRST (LIFO!)

  +--------------------------------------------+
  | FIX: push neighbors in REVERSE order       |
  |                                            |
  | WHEN ORDER MATTERS:                        |
  |   * Bridges / articulation points          |
  |   * SCC (Tarjan's)                         |
  |   * Problems comparing DFS trees           |
  |                                            |
  | WHEN IT DOESN'T:                           |
  |   * Reachability, connected components     |
  |   * Cycle detection (any order works)      |
  +--------------------------------------------+

---

Insight Gaps

Integrated from reflection notes

State-space BFS. Many harder problems run BFS on an implicit state space, not an explicit graph. The "nodes" are states (position, remaining_moves, color, ...) and "edges" are transitions:

  Explicit Graph BFS:          State-Space BFS:
  +---+    +---+               +----------+    +----------+
  | 1 |--->| 2 |               | (pos=1,  |--->| (pos=2,  |
  +---+    +---+               |  moves=3)|    |  moves=2)|
                               +----------+    +----------+
  Nodes = integers             Nodes = tuples of state
  Edges = adjacency list       Edges = valid transitions
  
  Key insight: BFS still gives shortest path in state-space,
  but you must model the state correctly:
    * Too little state --> wrong answers
    * Too much state   --> too many nodes (TLE/MLE)

BFS layers as structure. BFS naturally partitions nodes into layers (all nodes at distance 0, 1, 2, ...). This layer structure enables:

• 2-coloring / bipartite check
• Level graphs in Dinic's max-flow
• DAG construction from BFS tree

When DFS order matters. DFS with entry/exit times reveals the hierarchical structure of the graph -- not just connectivity:

  DFS on graph 1->2, 1->3, 2->4:
  
  Entry/Exit times:
  +------+-------+------+
  | Node | Entry | Exit |
  +------+-------+------+
  |  1   |   1   |  8   |
  |  2   |   2   |  5   |
  |  4   |   3   |  4   |
  |  3   |   6   |  7   |
  +------+-------+------+
  
  Node u is ancestor of v  <=>  entry[u] < entry[v] AND exit[v] < exit[u]
  
  Applications: SCC, bridges, Euler path, subtree queries

What the Code Won't Teach You

BFS layers reveal hidden structure. BFS doesn't just find shortest paths -- it partitions the graph into distance layers. This layering enables bipartite checking (odd cycle = not bipartite), level graphs in Dinic's max-flow, and DAG construction from BFS trees. Think "layer-by-layer" not just "explore all."

DFS reveals hierarchy, not just connectivity. With entry/exit times, DFS shows the nesting structure of the graph -- which nodes are ancestors/descendants of which. This is the foundation for subtree queries, Euler tour tricks, and all bridge/SCC algorithms. BFS cannot give you this.

State-space modeling is the real skill. The hard part of BFS/DFS problems at 1600+ is not the traversal -- it's defining the right state space. Too few state dimensions -> wrong answers. Too many -> TLE/MLE. Getting the state tuple right is the modeling skill that separates ratings.

  STATE-SPACE DESIGN CHECKLIST:

  +----------------------------------------------+
  | 1. What changes between moves?               |
  |    -> Each changing dimension = state variable|
  |                                              |
  | 2. Is the state space small enough?          |
  |    product of all dimensions <= ~10^7        |
  |                                              |
  | 3. Can I merge equivalent states?            |
  |    -> Reduces state space (e.g., symmetry)   |
  |                                              |
  | 4. Are there forbidden states?               |
  |    -> Don't visit them (prune early)         |
  +----------------------------------------------+

BFS layers encode parity -- and that unlocks bipartiteness. Every BFS edge connects nodes in the same layer or adjacent layers. A same-layer edge means an odd cycle exists and the graph is NOT bipartite. BFS bipartite checking is not "coloring" -- it's verifying the layer structure is consistent.

  BIPARTITE CHECK VIA BFS LAYERS:

  Layer 0    Layer 1    Layer 2
    (A)--------(B)--------(C)
     |                     |
     +--------(D)----------+
          Layer 1

  Edge A-D: layer 0 <-> layer 1 -> OK  (parity differs)
  Edge C-D: layer 2 <-> layer 1 -> OK  (parity differs)

  If ANY edge connects same-parity layers:
  --> NOT bipartite (odd cycle exists)

Estimating implicit graph size prevents TLE/MLE. Before coding state-space BFS, multiply the state dimensions. If the product exceeds ~${10}^7$, you need a smarter encoding or a different approach entirely.

  STATE-SPACE SIZE ESTIMATOR (decision flowchart):

       List all state dimensions
       (position, time, bitmask ...)
                  |
                  v
       Multiply them together
       = total number of states
                  |
                  v
          +---------------+
          |  > 10^7 nodes?|
          +---+-------+---+
             YES      NO
              |        |
              v        v
     +--------------+  +----------------+
     | STOP: rethink|  | BFS / DFS is   |
     | * merge sym- |  | feasible.      |
     |   metric     |  | Code it up.    |
     |   states     |  +----------------+
     | * drop a     |
     |   dimension  |
     | * use A* /   |
     |   pruning    |
     +--------------+

---

Hybrid Approaches

• Bidirectional BFS: Search from both source and target, meet in the middle. Reduces $O(b^d)$ to $O(b^{d/2})$.
• DFS + BFS: Use DFS to find components, then BFS within each component for shortest paths.
• Iterative Deepening DFS (IDDFS): Combines DFS space efficiency with BFS optimality. Rarely needed in CP but useful for unbounded search.

  CHOOSING YOUR TRAVERSAL VARIANT (decision flowchart):

  Need shortest path?
  +-- YES -> Unweighted graph?
  |          +-- YES -> Standard BFS
  |          +-- NO  -> Weights only 0 or 1?
  |                     +-- YES -> 0-1 BFS (deque)
  |                     +-- NO  -> Dijkstra / Bellman-Ford
  |
  +-- Multiple sources at distance 0?
  |   +-- YES -> Multi-source BFS (all sources in queue)
  |
  Need structural info?
  +-- Entry/exit times, subtree queries?
  |   +-- YES -> DFS
  |
  +-- Bridges / SCC / articulation points?
  |   +-- YES -> DFS (Tarjan's)
  |
  +-- Topological sort?
  |   +-- Need it online (edges added) -> Kahn's BFS
  |   +-- Otherwise -> DFS post-order
  |
  +-- Just reachability / connected components?
      +-- Either works (DFS is usually shorter to code)

---

Self-Test

Drawn from reflection notes

Without opening any reference:

1. Implement BFS from memory -- queue, visited marking, distance tracking. Test it on a 5-node graph you draw yourself.

2. Implement iterative DFS (not recursive) using an explicit stack. Know why this avoids stack overflow for $n>{10}^5$.

3. Explain the BFS shortest-path invariant -- why does BFS guarantee shortest path on unweighted graphs? Why does this fail on weighted graphs?

4. Write the 0-1 BFS template from memory -- deque-based, edges weight 0 or 1. Explain why it is $O(V+E)$ like BFS, not $O((V+E)\log V)$ like Dijkstra.

5. Name two DFS-specific properties (things BFS cannot give you) and two BFS-specific properties (things DFS cannot give you).

Quick self-checks:

• [ ] Can you implement BFS from memory in under 5 minutes, including distance tracking?
• [ ] Can you implement iterative DFS (explicit stack, not recursive) without reference?
• [ ] Can you explain why BFS guarantees shortest path on unweighted graphs but not weighted?
• [ ] Can you write the 0-1 BFS deque template from memory?
• [ ] Can you name 2 DFS-exclusive properties and 2 BFS-exclusive properties without looking?
• [ ] Can you implement multi-source BFS from memory -- all sources in queue at once, $O(V+E)$ total?
• [ ] Can you explain why naive iterative DFS reverses neighbor visit order (LIFO), and when this matters?
• [ ] Can you estimate a state-space BFS size before coding (multiply dimensions, check $\le {10}^7$)?
• [ ] Can you use BFS layers to check bipartiteness -- and explain why a same-layer edge means odd cycle?
• [ ] Can you convert a recursive DFS with backtracking into an iterative version preserving visit order?

6. Worked example -- multi-source BFS:

  Grid 4x4, sources at S, find distance to nearest S for every cell:
  
  +---+---+---+---+       +---+---+---+---+
  | S | . | . | . |       | 0 | 1 | 2 | 3 |
  +---+---+---+---+       +---+---+---+---+
  | . | . | . | . |  -->  | 1 | 2 | 3 | 4 |
  +---+---+---+---+       +---+---+---+---+
  | . | . | S | . |       | 2 | 1 | 0 | 1 |
  +---+---+---+---+       +---+---+---+---+
  | . | . | . | . |       | 3 | 2 | 1 | 2 |
  +---+---+---+---+       +---+---+---+---+
  
  Step 1: Push ALL sources into queue with dist=0
  Step 2: Standard BFS from there -- each cell gets
          distance to its NEAREST source automatically
  
  Why it works: BFS explores in distance order.
  The first time a cell is reached, it's from the closest source.

  BFS vs DFS PROPERTY MAP:

  +---------------------+----------+----------+
  | Property            |   BFS    |   DFS    |
  +---------------------+----------+----------+
  | Shortest path       |   Yes    |    No    |
  | Cycle detection     |  awkward |   Yes    |
  | Topological sort    |  Kahn's  |  natural |
  | Entry/exit times    |    No    |   Yes    |
  | Layer partitioning  |   Yes    |    No    |
  | Bipartite check     |   Yes    |   Yes    |
  | SCC / Bridges       |    No    |   Yes    |
  | Tree diameter       |   Yes    |   Yes    |
  | Connected comps     |   Yes    |   Yes    |
  | Backtracking        |    No    |   Yes    |
  +---------------------+----------+----------+

  Quick rule: need DISTANCE info? -> BFS
              need STRUCTURE info? -> DFS
              need just REACHABILITY? -> either (DFS simpler)

---

Cross-References

• BFS -- full coverage with 0-1 BFS, multi-source BFS
• DFS -- tree DFS, entry/exit times, back edges
• Topological Sort -- both BFS (Kahn) and DFS approaches
• Bridges -- DFS-based Tarjan's
• Data Structure Selection Guide
• Problem Pattern Recognition

---

What Would You Do If...?

1. The problem asks for minimum moves on a grid -- BFS or DFS?
2. You need to detect if a graph has a cycle -- BFS or DFS?
3. The graph has 10^6 nodes and you need connected components -- which is faster in practice?

The Mistake That Teaches

Grid problem: find minimum steps from (0,0) to (n-1,m-1). You write DFS with visited array, return the first path found. It works on small cases. On the contest test, it gives 17 instead of 12. DFS found A path, not the SHORTEST path. BFS was the right tool -- you knew this, but autopilot chose DFS.

---

Recap

• Shortest path (unweighted) = BFS. This is non-negotiable -- DFS does NOT find shortest paths.
• Structural analysis = DFS. Cycles, bridges, SCCs, entry/exit times, topological sort all need DFS.
• 0-1 BFS is not "BFS with a deque" -- it has a different correctness invariant (deque sorted by distance).
• Multi-source BFS: enqueue all sources at distance 0, run one BFS pass -- O(V+E), not O(k*(V+E)).
• Iterative DFS for large graphs: recursive DFS stack-overflows at n > 10^5; use explicit stack.
• State-space BFS: the hard part is defining the state tuple, not the traversal itself.