A graph is a set of nodes joined by edges: road maps, friendships, web links, dependencies between tasks. The edges here go both ways (the graph is undirected), and two nodes joined by an edge are neighbours.
Searching a graph means visiting every node reachable from a start node, without visiting any node twice. The two classic ways differ only in which node they explore next.
BFS spreads out in rings: everything one edge away, then two, and so on. So the first time it reaches a node is along a path with the fewest edges. Nodes are marked when they are added to the queue, not when processed, so no node is ever queued twice.
DFS follows one path as far as it goes before trying alternatives, like exploring a maze with one hand on the wall. The stack is exactly the path from the start to where you are. Written recursively, the call stack plays that role.
A not discovered yet B in the queue / on the stack C being processed D done
When a node has several neighbours to choose from, these pages always take them in alphabetical order. Any order gives a valid search; fixing one means each question has a single right answer.
| BFS | DFS | |
|---|---|---|
| Frontier | Queue (first in, first out) | Stack (last in, first out) |
| Explores | Ring by ring | One path as deep as possible, then backs up |
| Shortest paths? | Yes, by number of edges | No |
| Good for | Fewest-hops routes, levels, nearest matches | Cycles, topological order, connected components, mazes |
| Cost | O(V + E): each node is processed once and each edge looked at twice | |
For shortest paths when edges have different lengths, see Dijkstra's algorithm.