BFS vs DFS: The Difference, Visualized on a Grid

BFS uses a queue and spreads out from the start one layer at a time. DFS uses a stack and follows one branch as far as it can before backing up. Both visit every reachable node in O(V + E) time. The difference that usually decides between them is that BFS finds a path with the fewest edges on an unweighted graph, and DFS makes no such promise.

Run them yourself below. Both searches get the same grid, the same start and end, and the same neighbor order, so anything that differs comes from the queue and the stack, and from when each search marks a node.

BFS and DFS on the same grid

Around a wallOpen roomMazeNo path

BFS: a queue

S

E

Visited:

0 cells

Queue, next out first:

R2C2

Path:

not found yet

DFS: a stack

S

E

Visited:

0 cells

Stack, next out first:

R2C2

Path:

not found yet

S is the start and E is the end. Numbers give the visit order. Amber cells are waiting in the queue or stack, blue cells are visited, teal cells are the path, and dark cells are walls. R2C3 means row 2, column 3.

StepPlayResetStep 0 of 15

Ready. Both searches start at R2C2, look for R4C2 and check neighbors in the order up, right, down, left.

The comparison at a glance

	BFS	DFS
Frontier	Queue, first in, first out	Stack, last in, first out
Search shape	Layer by layer	One branch, then backtrack
Time	O(V + E)	O(V + E)
Extra space	O(V)	O(V), or O(E) if an explicit stack marks on removal
Finite graphs	Complete	Complete, with visited tracking
Fewest edges	Guaranteed when unweighted	Not guaranteed

V is the number of nodes and E is the number of edges.

Queue vs stack: the change that matters most

The two algorithms share a loop. Take a node off the frontier, look at its neighbors, and add the ones you have not seen. Most of the different behavior comes from which end of the frontier you take from. The rest comes from when each search marks a node as seen, which the code below shows.

A queue returns the oldest entry, so BFS finishes everything one edge from the start before touching anything two edges away. A stack returns the newest entry, so DFS always continues from the node it just discovered and only returns to older entries when a branch runs out.

function bfs(neighbors, start, end) {
  const queue = [start]
  const parents = new Map([[start, start]])
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head]
    if (node === end) return parents
    for (const next of neighbors(node)) {
      if (parents.has(next)) continue
      parents.set(next, node)
      queue.push(next)
    }
  }
  return null
}

function dfs(neighbors, start, end) {
  const stack = [[start, start]]
  const parents = new Map()
  while (stack.length) {
    const [node, parent] = stack.pop()
    if (parents.has(node)) continue
    parents.set(node, parent)
    if (node === end) return parents
    // Reversed, so the first neighbor comes off the stack first.
    for (const next of [...neighbors(node)].reverse()) {
      if (!parents.has(next)) stack.push([next, node])
    }
  }
  return null
}

Both return a map of parents. Walk it back from end to start to get the path.

The marking differs on purpose. BFS can mark a node when it first discovers it, because the earliest discovery is already the shortest route there. DFS marks a node when it comes off the stack, because a later discovery should be explored first. A DFS that marks on discovery still reaches the same cells, but it does not visit them in the order a recursive DFS would.

A worked example on a grid

These numbers come from running the module behind the visualizer on its first board, Around a wall. The grid has 4 rows and 4 columns, one wall, and 15 open cells. S is the start at R2C2, and E is the end at R4C2, directly below the wall. Both searches check neighbors in the order up, right, down, left.

     C1  C2  C3  C4
R1    .   .   .   .
R2    .   S   .   .
R3    .   #   .   .
R4    .   E   .   .

The first visit looks the same for both: R2C2, leaving R1C2, R2C3 and R2C1 waiting. The second visit is where they separate. Each search moves to R1C2 and finds R1C3 and R1C1. BFS puts them at the back of the line, and DFS puts them at the front.

BFS, with the queue listed next out first:

Visit	Cell	Queue after the visit
1	R2C2	R1C2, R2C3, R2C1
2	R1C2	R2C3, R2C1, R1C3, R1C1
3	R2C3	R2C1, R1C3, R1C1, R2C4, R3C3
4	R2C1	R1C3, R1C1, R2C4, R3C3, R3C1

DFS, with the stack listed next out first:

Visit	Cell	Stack after the visit
1	R2C2	R1C2, R2C3, R2C1
2	R1C2	R1C3, R1C1, R2C3, R2C1
3	R1C3	R1C4, R2C3, R1C1, R2C1
4	R1C4	R2C4, R2C3, R1C1, R2C1

R2C3 jumps ahead of R1C1 at visit 3 because R1C3 discovered it again, and the newer entry is on top of the stack.

The full runs end like this:

• BFS visits R2C2, R1C2, R2C3, R2C1, R1C3, R1C1, R2C4, R3C3, R3C1, R1C4, R3C4, R4C3, R4C1, R4C4, R4C2. Its path takes 4 steps: R2C2, R2C3, R3C3, R4C3, R4C2.
• DFS visits R2C2, R1C2, R1C3, R1C4, R2C4, R3C4, R4C4, R4C3, R3C3, R2C3, R4C2. Its path takes 8 steps: R2C2, R1C2, R1C3, R1C4, R2C4, R3C4, R4C4, R4C3, R4C2.

BFS visited more cells and found the shorter path. DFS visited fewer cells and returned a path twice as long. Neither result is a general rule about visit counts, as the other boards show:

Board	BFS visits	BFS path steps	DFS visits	DFS path steps
Around a wall	15	4	11	8
Open room	4	1	24	23
Maze	26	13	21	13
No path	16	None	16	None

On the Open room board the end sits right next to the start, one cell below it. BFS finds it almost immediately. DFS goes up first and winds around the room for 23 steps. On the Maze board the two paths match, which comes from that layout and is not something DFS can promise. On the No path board both searches visit all 16 cells they can reach and then stop.

Shortest paths on unweighted graphs

BFS removes nodes in order of their distance from the start, so all nodes at distance 1 leave the queue before any at distance 2. The first time it reaches a node, it has used as few edges as possible. That makes the path to the end a shortest one, as long as every edge counts the same.

There can be several shortest paths. Neighbor order decides which one BFS returns, not how long it is.

DFS stops at the first route it completes, and nothing about a stack makes that route short. It can return the shortest path on a given board, as the Maze board shows, but you cannot rely on that without checking every other route.

Time and space complexity

Both algorithms handle each node once and look at each edge a constant number of times, which gives O(V + E) time with an adjacency list. On a grid, V is rows × columns and each cell has at most four neighbors, so that simplifies to O(rows × columns). Worst-case time is the same, but real run time depends on where the target is, because either search can stop early.

Space is where the two tend to feel different:

• BFS holds the current layer and part of the next one. On a wide graph that can be most of the nodes. On a tree with branching factor b and a target at depth d, the queue can reach about b^d entries.
• DFS depends on how it is written. The explicit stack in the code above holds the untried neighbors of the nodes on the current branch, not the branch itself. On a tree with maximum depth m, that is about b × m entries, which is far smaller on a wide, shallow tree. Recursive DFS holds one call frame for each node on the current branch, about m frames on that tree. On a long, thin graph the two split: walking a path of 1,000 nodes from one end, recursion reaches 1,000 frames while the explicit stack holds 1 entry.

Recursive DFS keeps its frames on the call stack, so a deep enough graph can overflow it. An explicit stack avoids that limit. An explicit stack that marks on removal can also hold duplicate entries, up to one per edge.

Completeness

A search is complete if it finds a solution whenever one exists. On a finite graph, both BFS and DFS are complete as long as they track visited nodes. Without that tracking, DFS can loop around a cycle forever.

On an infinite graph they differ. BFS still finds any target at a finite depth when each node has finitely many neighbors, because it reaches every depth in turn. DFS can follow an endless branch and never come back.

When to use BFS or DFS

Pick BFS when you need:

• The path with the fewest edges or moves, such as the fewest moves through a maze or the fewest hops between two accounts in a network.
• Whatever is nearest to the start first.
• Results grouped by distance, such as printing a tree level by level.

Pick DFS when you need:

• To try complete options and back up, as in puzzle solvers and generating permutations.
• Cycle detection, which relies on knowing which nodes are still on the current branch, or a topological sort, which relies on the order nodes finish in.
• Any path at all on a graph with very wide layers, where a BFS queue would get large.

Either one works when you only need to know what is reachable. Counting connected components and flood fill visit the same cells with either search, just in a different order. Revealing the open area around a 0 in Minesweeper is that kind of problem: the same cells open whichever order you use.

Common questions

Is BFS faster than DFS?

Not in general. Their worst-case time is the same. In the table above BFS visits 4 cells to DFS's 24 on one board, and 15 to DFS's 11 on another. BFS tends to win when the target is close to the start, and DFS can win when it happens to head toward a distant target.

Does DFS ever find the shortest path?

It can, by chance, but it does not guarantee one. To get a shortest path on an unweighted graph, use BFS.

Which uses less memory?

It depends on the graph's shape and on how DFS is written. DFS is usually smaller on wide, shallow graphs. On long, narrow graphs BFS can be smaller than recursive DFS, which needs a call frame for each node on the current branch, while an explicit stack can stay as small as the queue.

Why does neighbor order matter?

It changes the visit order for both searches. For BFS it can change which shortest path you get but not the length. For DFS it can change the length of the path too. That is why the visualizer uses one fixed order for both.