---
name: dfs-vs-bfs
description: "Choose between DFS and BFS for graph traversal problems. Use when deciding whether to explore depth-first (cycle detection, paths) or breadth-first (shortest path, levels)."
topic: Graph Traversal
token_cost: 100
related: [bfs-state-space, recursion-backtracking]
keywords:
  [
    dfs,
    bfs,
    depth,
    breadth,
    graph,
    traverse,
    path,
    maze,
    shortest,
    connected,
    reachable,
    visited,
    queue,
    stack,
    neighbor,
    walk,
    flood,
    fill,
    island,
  ]
---

## When to use

DFS (stack/recursion) explores one branch fully before backtracking. BFS (queue) explores level-by-level.

## Rules

- If the problem asks "shortest" or "minimum steps" on an unweighted graph, ALWAYS choose BFS
- If it asks "all paths," "can we reach," or "count islands," DFS is simpler
- NEVER use BFS for cycle detection — DFS is the right tool
- Both visit each node once: O(V+E) time

## DFS use cases

Cycle detection, topological sort, path existence, connected components, backtracking puzzles, flood fill.

## BFS use cases

Shortest unweighted path, level-order traversal, nearest neighbor, minimum steps.

## Example

"Count islands" → DFS flood-fill on 2D grid. "Shortest path in maze" → BFS with queue tracking (row, col, distance).