BFS vs DFS: two ways to traverse a graph
Same graph, two visit orders — breadth-first sweeps level-by-level, depth-first dives down each branch first.
What this shows
Both BFS and DFS visit every node reachable from a starting node exactly once, but they pick which node to visit next using different rules:
BFS: use a queue (FIFO). Visit closer nodes first.
DFS: use a stack (LIFO). Dive into one branch before
backtracking to siblings.On the seven-node tree-like graph in the figure, starting from A:
BFS order: A, B, C, D, E, F, G
(level 0: A; level 1: B, C; level 2: D, E, F, G) DFS order: A, B, D, E, C, F, G
(dive A → B → D, back up, B → E, back up,
then A → C → F, back up, C → G)The only algorithmic difference is the choice of queue vs stack for the "frontier" of nodes still to process. Everything else — the visited set, the loop structure, the per-node work — is identical.
Where it shows up
BFS is the right choice when you want the *shortest* path in an unweighted graph: the first time BFS reaches a node, it has done so along a minimum-edge-count route. Web crawlers use BFS to keep recently-discovered URLs balanced across the crawl.
DFS is the right choice when you want to explore a tree structure compactly (using O(depth) memory instead of O(breadth)), to find cycles, to topologically sort a DAG, or to compute strongly connected components via Tarjan's or Kosaraju's algorithms. Iterative-deepening DFS combines DFS's low memory with BFS's optimality and is the basis of many classical AI search algorithms.
Frequently asked questions
Does the start node have to be a specific one?
No — you can run BFS or DFS from any vertex. If the graph isn't connected, you'll only visit the component containing the start. To visit every node, run the traversal once per unvisited node in an outer loop.
What about for weighted graphs?
BFS only finds shortest paths in *unweighted* graphs (or graphs where every edge has the same weight). For positive-weight graphs you need Dijkstra's algorithm; for graphs with negative weights, Bellman-Ford. Both can be seen as generalisations of BFS that respect edge weights.
Does the order in which children are queued/pushed matter?
It changes the visit order but not the correctness of either algorithm. Both still visit every reachable node exactly once. For deterministic test cases, traversals usually process children in alphabetical or insertion order.
How do BFS and DFS relate to Dijkstra and A*?
Dijkstra's algorithm is BFS with a priority queue keyed on accumulated distance, and A* is Dijkstra with a heuristic added to the priority. All three explore a frontier of nodes; they differ only in how they decide which frontier node to expand next.