Breadth-first search and depth-first search visit the same graph in different orders. The right choice follows from the information the problem asks you to preserve.
Choose breadth-first search
BFS explores by distance from the start. In an unweighted graph it naturally finds a path with the fewest edges. It is also a good fit for level-order tree traversal, minimum-step transformations, and problems where the earliest reachable state is the answer.
Choose depth-first search
DFS follows one branch before returning. It fits exhaustive exploration, connected components, cycle detection, topological reasoning, backtracking, and tree calculations that depend on child results. Its recursive form can be concise, although an explicit stack avoids recursion-depth limits.
Explain the trade-off
Both traversals are typically linear in vertices plus edges when adjacency lists are used. Their memory profiles differ with graph shape: BFS may hold a wide frontier, while DFS may hold a deep path. Always track visited states unless revisiting is intentional, and clarify whether the graph is directed.
Continue with the book
Explore the full treatment, worked examples, and exercises in Algorithmic Edge.
Adapted from Algorithmic Edge, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.