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.
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.
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.
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.