Skip to content
BENIBIX Learn

BFS vs DFS

Breadth-first search walks a graph one layer at a time and finds the path with the fewest steps. Depth-first search follows one path to its end, then backs up.

Development🧮 Algorithms & Data Structures

Breadth-First Search (BFS)

Walking a graph one layer at a time, nearest nodes first.

Breadth-first search walks a graph or tree one layer at a time. It visits every neighbour of the start, then every neighbour of those, and so on. It keeps the nodes it has yet to visit in a queue. Because it goes layer by layer, it finds the path with the fewest steps first. It marks each node it has seen, so loops cannot trap it.

Example
Emma's app finds how many steps away Jack is in her friend graph. BFS checks her friends, then theirs, and finds him at step 2.
Why it matters
It is the standard way to find the shortest path when every step costs the same.
Full entry
Development🧮 Algorithms & Data Structures

Depth-First Search (DFS)

Walking a graph down one path as far as it goes, then backing up.

Depth-first search walks a graph or tree by going as deep as it can down one path first. When it hits a dead end, it steps back and tries the next branch. It keeps its place with a stack, or by calling itself with recursion. It is good for checking if two nodes connect, finding loops and solving puzzles. It does not promise the shortest path.

Example
Jack's puzzle solver tries one move after another until it gets stuck. Then it backs up one move and tries the next one.
Why it matters
Many puzzle solvers and maze games are built on it.
Full entry

In one line

Breadth-First Search (BFS)
Walking a graph one layer at a time, nearest nodes first.
Depth-First Search (DFS)
Walking a graph down one path as far as it goes, then backing up.