Interactive Math & Science Lessons

BFS vs DFS Visualizer

Watch how BFS and DFS explore the same graph differently. BFS goes wide, DFS goes deep.

Loading interactive simulation...

BFS finds the shortest path only when every edge costs the same 🖖

The usual reason to reach for BFS is that it returns the shortest route. That guarantee is narrower than it sounds: it holds because BFS treats every edge as one step, so the first time it reaches a node it must have arrived by the fewest possible hops. Attach real costs — road distances, transfer fees, latency — and the guarantee evaporates. BFS will still answer confidently, and it will be wrong, because a two-hop path over expensive edges can easily cost more than a five-hop path over cheap ones. Dijkstra’s algorithm is the repair, and it is almost exactly this: BFS with the plain queue swapped for a priority queue.

Same map, two travel styles 🖖

Run both side by side and they visit the exact same nodes and the exact same edges, in a different order. BFS explores its whole current neighbourhood before venturing further, so it has to remember every node waiting on the frontier. DFS commits to one branch and only tracks the path it is on. On the binary tree that is 8 nodes queued against a stack 4 deep. Reach for BFS when the answer is likely close by, and DFS when the graph is deep and you want to keep memory small.

Both algorithms were born in mazes 🖖

Long before computers, DFS existed as a maze-walking rule published by the French mathematician Charles Pierre Trémaux in the 1800s. BFS arrived much later: Edward F. Moore reinvented it in a 1959 paper literally titled The Shortest Path Through a Maze, and Konrad Zuse had already sketched it in 1945. Two cornerstone algorithms of computer science, both first devised simply to escape a labyrinth.

GRAPH TRAVERSAL — WHICH ORDER DO YOU NEED, AND WHAT DOES IT COST?

Which Traversal Case Are You In?

BFS and DFS visit the same nodes and differ in one line of code: a queue instead of a stack. Everything else follows from that. The queue spreads outward in rings, so the first time BFS reaches a node it has taken a fewest-edges path there. The stack dives, so DFS reaches the far end sooner but by no particular route. Which you want depends on the question — and on the shape of the graph, which decides what each one costs.

You need the fewest edges — BFS, because it visits in distance layers FIFO ⇒ min |E|
A tree — level order against pre-order, and the memory cost reverses BFS: O(w), DFS: O(d)
A chain — the two orders coincide and the choice stops mattering deg ≤ 2 ⇒ BFS = DFS
Not everything is reachable — one starting node is not enough c(G) > 1

01

You need the fewest edges — BFS, because it visits in distance layers

What you know: An unweighted graph and a shortest-path question. BFS visits everything at distance 1, then everything at distance 2, so the first arrival at a node is along a shortest path.

Rule: FIFO ⇒ min |E|

Worked example: On the 4×4 grid from node 0, BFS visits 0, 1, 4, 2, 5, 8, 3, 6, 9, 12, … — a diagonal wavefront. DFS visits 0, 1, 2, 3, 7, 6, 5, 4, … and reaches node 4 only on its eighth step.

Open this case: 4x4 Grid
You need the fewest edges — BFS, because it visits in distance layers. BFS sweeps outward in distance layers; DFS snakes down one corridor before coming back. An unweighted graph and a shortest-path question. BFS visits everything at distance 1, then everything at distance 2, so the first arrival at a node is along a shortest path.
BFS sweeps outward in distance layers; DFS snakes down one corridor before coming back.

02

A tree — level order against pre-order, and the memory cost reverses

What you know: On a tree the two orders have names: BFS is level order, DFS is pre-order. Both visit all 15 nodes; what differs is how much has to be held at once.

Rule: BFS: O(w), DFS: O(d)

Worked example: BFS gives 0, 1, 2, 3, …, 14 — each level in turn. DFS gives 0, 1, 3, 7, 8, 4, 9, 10, 2, … — down the left spine first. Peak queue 8, peak stack 4.

Open this case: Binary tree
A tree — level order against pre-order, and the memory cost reverses. Level order fills each row before moving down; pre-order runs to a leaf and backs up. On a tree the two orders have names: BFS is level order, DFS is pre-order. Both visit all 15 nodes; what differs is how much has to be held at once.
Level order fills each row before moving down; pre-order runs to a leaf and backs up.

03

A chain — the two orders coincide and the choice stops mattering

What you know: Every node has exactly one unvisited neighbour, so there is only one way forward. BFS and DFS produce the identical sequence and hold one node at a time.

Rule: deg ≤ 2 ⇒ BFS = DFS

Worked example: On the 12-node chain both visit 0, 1, 2, …, 11 in that order, and both frontiers stay at size 1 from start to finish.

Open this case: Long chain
A chain — the two orders coincide and the choice stops mattering. With nothing to branch into, both traversals walk the same line in the same order. Every node has exactly one unvisited neighbour, so there is only one way forward. BFS and DFS produce the identical sequence and hold one node at a time.
With nothing to branch into, both traversals walk the same line in the same order.

04

Not everything is reachable — one starting node is not enough

What you know: The graph comes in pieces. Started from one node, either traversal visits only the component that node belongs to, and then stops.

Rule: c(G) > 1

Worked example: From node 0 of the 10-node graph, both BFS and DFS visit exactly 4 nodes and halt. Nodes 4, 5, 6, 7, 8 and 9 are never touched.

Open this case: Disconnected
Not everything is reachable — one starting node is not enough. Four nodes reachable and six not: one start explores one component and no more. The graph comes in pieces. Started from one node, either traversal visits only the component that node belongs to, and then stops.
Four nodes reachable and six not: one start explores one component and no more.
References (2)
  • Insight block 3 — BFS as a maze algorithm: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.
  • Trémaux's rule, as it was actually published: É. Lucas, Récréations mathématiques, vol. 1. Gauthier-Villars, Paris, 1882 — Lucas credits the maze-walking procedure to Charles Pierre Trémaux.

Problem solved in full

  1. A traversal of a maze holding 16 nodes and 16 edges 5 steps

    The maze holds 16 nodes joined by 16 edges. Work out how many nodes a traversal starting at node 0 reaches, and how far node 15 is from node 0. This is the Maze corridor state with start node 0.

    1. Write the maze out as an adjacency list before doing anything else. Node 4 is the one worth noticing: not a single edge touches it, so its degree is 0 and no traversal starting anywhere else will ever land on it.

    2. Breadth-first search sorts what it can reach into layers, layer k being everything first met from layer k − 1. Building them is a closure rather than a walk — you finish a layer completely before opening the next, and no node appears twice.

    3. Add the layer sizes. The traversal reaches 15 nodes, one short of the 16 the graph contains, and that is why the step counter stops one below the node count.

    4. Node 15 first appears in layer 6, and a layer number is a distance: a node is only ever enqueued from a node one layer above it, so nothing in layer 6 can be reached in fewer than 6 edges. The route 0-1-5-6-7-11-15 achieves 6, so the bound is exact.

    5. Depth-first search carries no such invariant. Let the walker take 5 before 2 at node 1, then 9 before 6 at node 5, then 8 before 10 at node 9, each of them a legal choice between unvisited neighbours, and it commits to the long corridor, backtracking only once it runs out of graph. It meets node 15 at the far end of a 12-edge path, and that path is a perfectly valid answer to the reachability question.

    Answer

    Node 15 sits 6 edges from the start, and a depth-first walk can hand you a route of 12 to the same place. The factor of 2 is not the interesting part; where a shortcut can come from at all is. The reachable component holds 15 nodes, so any spanning tree of it uses 14 edges — and the maze has 16, which means exactly 2 edges are surplus. Delete those 2 and what remains is a tree, where there is precisely one path between any pair of nodes, so the two panels would then agree on every distance and differ only in the order they walk. Every disagreement about distance between them traces back to those 2 extra edges. It is also the reason depth-first is the cheaper habit when the question is merely whether a node is reachable, and the wrong one the moment the question becomes how far.

· Updated

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

  • 4x4 Grid - 4×4 grid: BFS spreads in diagonal layers of 1, 2, 3, 4, 3, 2, 1 nodes, reaching the far corner in 6 hops.
  • Maze corridor - DFS walks 12 corridors before it stands on node 15. BFS proves the way there is 6. Same maze, twice the walk.
  • Star graph - Nine spokes, every node one hop from the hub. Depth-first has nowhere to go deep, so it returns the same order BFS does.
  • Long chain - Twelve nodes in a line: the orders match again, but here each algorithm holds one node at a time against the star's nine.
  • Binary tree - Complete binary tree: the BFS queue peaks at 8, the whole bottom level, while the DFS stack never exceeds 4.
  • Disconnected - Two squares and two stranded nodes. A traversal from node 0 reaches 4 of the 10, and no amount of searching finds the rest.
  • Dense graph - 8 nodes, 13 edges, and node 7 is still 3 hops out: dense at this size does not mean everything is close.