Both breadth-first and depth-first search visit every node reachable from a starting point exactly once, in O(V + E) time, using O(V) space. Same graph, same nodes, same edges, same asymptotic cost. The entire difference between them — which shows up in the order nodes get visited, and in which real problems each one actually solves — comes down to a single choice: what data structure holds the frontier of nodes still waiting to be explored. BFS uses a queue. DFS uses a stack.
The same graph, two orders
Take a small tree: node 0 connects to 1 and 2, node 1 connects to 3, node 2 connects to 4. Start both algorithms at node 0 and visit neighbors in numeric order:
graph: 0–1, 0–2, 1–3, 2–4
BFS's queue is FIFO — the earliest-discovered node gets processed first, which is exactly what makes it expand outward one whole layer at a time: visit 0, discover 1 and 2 (layer 1), then visit all of layer 1 before touching layer 2. DFS's stack is LIFO — the most recently discovered node gets processed next, which sends it plunging down one branch (0 → 1 → 3) all the way to a dead end before it ever backtracks to try the other branch (0 → 2 → 4). Same edges. Opposite instincts.
Why BFS finds shortest paths — in one specific sense
Because BFS finishes an entire layer before starting the next one, the first time it reaches any node is guaranteed to be via the fewest possible edges from the start. That makes it the right tool for shortest path by edge count in an unweighted graph — fewest hops, not fewest total distance. The moment edges carry different weights, that guarantee evaporates: a path with more hops can easily have less total weight than a path with fewer. That's a different problem with different algorithms — Dijkstra's algorithm for non-negative weights, Bellman-Ford when weights can go negative — not a variant of BFS.
Why DFS suits cycle detection, topological sort, and components
DFS's habit of committing fully to one branch before backtracking turns out to be exactly the right shape for a different family of problems. Detecting a cycle in a graph comes down to noticing a back edge — an edge to a node that's already been discovered but hasn't finished yet, meaning it's still an ancestor on the current path. A topological sort of a directed acyclic graph falls out of recording each node's finish time and reading them in reverse — nodes with no outstanding dependencies naturally finish first. Finding connected components is just running DFS (or BFS — this one doesn't care) from every undiscovered node and counting how many times you had to restart. None of these need shortest-path information; they need to know the graph's shape, and DFS's depth-first commitment exposes that shape directly.
DFS's hidden cost: the call stack
The most natural way to write DFS is recursive — visit a node, then recurse into each unvisited neighbor — which means the "stack" in depth-first search is usually the real call stack, one frame per node currently on the path from the root. For a balanced tree that's a shallow O(log n) depth and genuinely free. For a long skewed chain, or an adversarially deep input, that's O(V) stack depth — the same cost recursion vs iteration covers for recursion in general, just wearing a graph-shaped costume. An iterative DFS with an explicit array-as-stack fixes the recursion limit but not the space cost — it just moves those V frames from the call stack to a data structure you can see, which is the same "relocated, not removed" trade-off recursive tree traversal runs into.
Practical guidance
- Need the fewest hops between two nodes, unweighted? BFS. It's the only one of the two with that specific guarantee.
- Edges have weights? Neither. Reach for Dijkstra's algorithm (non-negative weights) or Bellman-Ford (negative weights allowed).
- Detecting a cycle, topological sort, finding connected components? DFS — its finish-time ordering and back-edge detection are built for exactly this family.
- Graph could be very deep or adversarially structured? Prefer BFS, or an iterative DFS with an explicit stack — plain recursive DFS is one pathological input away from a stack overflow.
- Just need to visit everything — no shortest-path or ordering requirement? Either works; pick whichever is already implemented, or whichever visit order is easier to reason about for the rest of your code.
Try it yourself
Graph Traversal Visualizer runs BFS and DFS on the same randomly generated graph, step by step — watch the queue or call stack change after every edge check, and see each node move from undiscovered to discovered to finished. For the guaranteed-acyclic structure BFS/DFS never has to worry about, see Tree vs Graph. For the call-stack cost behind recursive DFS specifically, see Recursion vs Iteration. All tools run entirely in your browser.