Breadth-first search (BFS) explores a graph outward one distance layer at a time; depth-first search (DFS) follows one branch as far as it can before backtracking. That distinction matters most when looking for a shortest path: BFS finds a path with the fewest edges in an unweighted graph, while DFS does not guarantee one.
How BFS and DFS explore a graph
Imagine a graph as locations connected by links. Starting from one vertex, BFS first visits its immediate neighbors, then vertices two edges away, then those three edges away, and so on. MIT’s Spring 2020 6.006 Recitation 10 notes describe BFS as discovering reachable vertices “level-by-level outward” from the start.
| # | Preview | Product | Price | |
|---|---|---|---|---|
| 1 |
|
Introduction to Algorithms, fourth edition | $91.50 | Buy on Amazon |
| 2 |
|
Algorithms (4th Edition) | $68.77 | Buy on Amazon |
| 3 |
|
Introduction to Algorithms, 3rd Edition | $99.99 | Buy on Amazon |
| 4 |
|
Algorithms | $124.77 | Buy on Amazon |
| 5 |
|
Algorithm Design | $222.95 | Buy on Amazon |
DFS instead selects an available neighbor and continues deeper along that branch. When it reaches a vertex with no unvisited neighbors, it backtracks and tries another branch. The precise visit order can depend on how neighbors are ordered, but the two algorithms’ defining difference remains: BFS expands by distance layers, while DFS prioritizes depth.
DFS vs. BFS at a glance
| Question | BFS | DFS |
|---|---|---|
| How does it proceed? | Visits vertices in increasing numbers of edges from the start. | Follows a branch deeply, then backtracks to explore alternatives. |
| Typical implementation | FIFO queue: process the earliest discovered vertex first. | LIFO stack, or recursion using the call stack. |
| Does it guarantee a shortest path? | Yes, by number of edges in an unweighted graph. | No. It may find a path, but not necessarily one with the fewest edges. |
| Common uses | Unweighted shortest paths, distances from a source, and level-by-level exploration. | Topological sorting, cycle detection, connected components, and structural analysis. |
| Traversal time | O(V + E) for a full adjacency-list traversal. | O(V + E) for a full adjacency-list traversal. |
| Memory considerations | The queue frontier can become large; total memory also depends on stored graph and traversal data. | The stack or recursion depth can grow with search depth; total memory also depends on stored graph and traversal data. |
Here, V is the number of vertices and E is the number of edges. The time bounds are theoretical analysis for adjacency-list implementations, not empirical benchmarks. A search started from one source processes only the vertices and edges reachable from that source; traversing a disconnected graph in full requires starting again from each unvisited vertex.
#1 Best Overall
- color: White
- INTRODUCTION TO ALGORITHMS, FOURTH EDITION
Which one finds the shortest path?
For an unweighted graph, BFS finds a path with the fewest edges from the start to each reachable vertex. Its layer order is the reason: it finishes considering vertices one edge away before two edges away, and so forth. If you need the actual route, record each vertex’s predecessor when it is first discovered, then follow those predecessor links backward from the destination.
DFS can find a route if one exists, but the route in its search tree is not generally shortest. MIT’s Recitation 10 notes make the same distinction between BFS and DFS trees in an unweighted graph.
Rank #2
For example, suppose the start has a goal as one immediate neighbor and also a separate branch that continues for many edges. DFS might follow the long branch first, depending on neighbor order; BFS visits the immediate neighbors before exploring farther away. A different neighbor order can change the exact DFS sequence, but not BFS’s fewest-edge guarantee.
This guarantee is about edge count, not general travel cost. If edges have unequal costs and you want the minimum-cost route, ordinary BFS is not the right guarantee; use a shortest-path algorithm designed for weighted edges.
Recommended Free Tools
Rank #3
- Hard Cover
When to choose each traversal
Choose BFS for distance and nearest-path questions
- Find a path with the fewest edges in an unweighted graph.
- Measure the number of steps from a source to reachable vertices.
- Process a graph by layers or identify what is reachable within a given number of edges.
Choose DFS for deep exploration and graph structure
- Explore a branch fully before returning to alternatives.
- Support graph analyses such as topological sorting and cycle detection.
- Find connected components or examine structural relationships.
Either traversal can answer a basic reachability question—whether a vertex can be reached from the start. Choose based on whether distance layers or deep exploration better fits the task.
Implementation details that prevent common errors
Track discovered vertices
Use a visited set or equivalent state so cycles do not make the traversal run indefinitely. Mark a vertex discovered when you enqueue it for BFS or push it for iterative DFS, rather than waiting until it is removed for processing. This prevents the same vertex from being added repeatedly when paths converge or cycles are present.
Rank #4
Account for disconnected graphs
A traversal from one source reaches only that source’s connected, reachable portion. To visit every vertex in a disconnected graph, iterate over all vertices and start a new traversal whenever you find one that remains unvisited.
Choose recursion or an explicit stack for DFS
Recursive DFS is concise, but a very deep graph may exceed a programming language’s call-stack limit. An explicit stack avoids relying on recursion depth. This is an implementation choice; DFS is defined by its depth-first behavior, not by a requirement to use recursion.
Quick wins for a faster PC:
Scan for outdated or missing drivers - takes under a minuteDriver Scan →Repair Windows errors before they cause bigger problemsFix Now →Best Value
Understand what the space bound counts
Memory use depends on whether the calculation includes the graph representation, visited markers, parent data, and the queue, stack, or recursive call state. Princeton’s Algorithms 4/e cheatsheet lists V extra space for its implementations, excluding the graph. That specific accounting should not be turned into a blanket claim that DFS always uses less memory: graph shape and implementation affect how large the active frontier or depth becomes.
Independent reader supportYour contribution helps us test, update, and keep practical guides available for everyone.Time complexity and further references
With adjacency lists, a full BFS or DFS traversal has O(V + E) time complexity: vertices are visited and their incident adjacency entries are examined. For Princeton’s BFS reference, see Undirected Graphs. MIT’s Lecture 10: Depth-First Search covers DFS and its analysis. Princeton’s course readings also point readers to graph-algorithm study materials.
Quick Recap
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
