BFS vs DFS: How Each Works, Complexity and Which to Use for Which Problem
Key takeaways
Compare BFS and DFS from the perspective of working principles, time complexity, and space complexity. Learn selection criteria for shortest path, cycle detection, and more in real-world scenarios.
Introduction
“Should I use BFS or DFS?” This is the most common question when solving graph problems. In this article, we’ll clearly understand the differences between BFS and DFS and learn how to choose the right algorithm for different problem types. To use an analogy, BFS is like an elevator guide that checks all the same distance (floor) first, while DFS is like maze exploration or backtracking that follows one branch to the end before returning. If shortest distance is important, use the level-spreading approach (BFS); if you need to deeply test all branches, use the one-branch-at-a-time approach (DFS).
The two are closer than they look: the same loop with a queue is BFS and with a stack is (a form of) DFS. What differs is the order in which the frontier is expanded, and that order is what gives each one its guarantees. BFS finishes every vertex at distance d before touching any vertex at distance d + 1, which is exactly why the first time it reaches a target is along a shortest path. DFS finishes a vertex only after everything reachable from it is finished, which is what cycle detection and topological sorting rely on.
Quick Comparison
| Feature | BFS | DFS |
|---|---|---|
| Data Structure | Queue | Stack or Recursion |
| Traversal Order | Level order (nearest first) | Depth first (to the end) |
| Shortest Path | ✅ Guaranteed (unweighted graph) | ❌ Not guaranteed |
| Memory | O(w) (width) | O(h) (height) |
| Implementation | Iteration | Recursion or Iteration |
| Use Cases | Shortest path, level traversal | Cycle detection, path existence |
Performance, Usability, and Application Scenarios (At a Glance)
| Category | BFS | DFS |
|---|---|---|
| Performance (Time) | Both traverse the entire graph once, O(V+E) level | Same |
| Performance (Space) | Queue can hold one level’s worth of nodes, burden in wide graphs | Recursion stack or explicit stack depth. Be careful of stack limits in very deep graphs |
| Usability | Distance/level concept directly appears in code, intuitive for shortest distance problems | Easy to dive in with one recursion, convenient for backtracking and connected components |
| Application Scenarios | Unweighted shortest path, bipartite graph check, level traversal | Topological sort, cycle/strongly connected components, “all cases” exploration |
When to Use BFS, When to Use DFS?
- Consider BFS when: You need minimum moves or minimum edges from a starting point, or when you need to process nearest vertices first.
- Consider DFS when: Rather than shortest distance, reachability, all paths/combinations, or structural properties of trees/graphs (cycles, topological order) are key.
- For problems where both work, consider implementation difficulty and memory constraints (DFS may be more favorable for wide graphs).
How It Works
BFS: Breadth-First Search
Code Flow: Put the starting vertex in the queue and mark it as visited, then take vertices from the front of the queue and add unvisited adjacent vertices to the queue. This visits nearest distances first in order.
Graph:
1
/ \
2 3
/ \ \
4 5 6
BFS Order: 1 → 2 → 3 → 4 → 5 → 6
(Level 0) (Level 1) (Level 2)void BFS(int start) {
queue<int> q;
vector<bool> visited(n, false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
// Explore adjacent vertices
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}The line that matters most is visited[v] = true at push time. Marking when a vertex is popped instead still gives correct answers, but a vertex can then be pushed once per incoming edge before it is ever popped, so the queue grows to O(E) instead of O(V), and on dense graphs or big grids that is the difference between passing and a memory or time limit. It also breaks the distance guarantee in variants that record the distance at push time.
DFS: Depth-First Search
Code Flow: Mark the current vertex as visited, then recursively dive first into unvisited adjacent vertices. Since it goes to the end of one branch before moving to other siblings, the visit order differs from BFS.
Graph:
1
/ \
2 3
/ \ \
4 5 6
DFS Order: 1 → 2 → 4 → 5 → 3 → 6
(Depth first)void DFS(int u, vector<bool>& visited) {
visited[u] = true;
cout << u << " ";
for (int v : adj[u]) {
if (!visited[v]) {
DFS(v, visited);
}
}
}Time/Space Complexity
Time Complexity
Both O(V + E)
- V: Number of vertices
- E: Number of edges
- Visit all vertices and edges once
Space Complexity
Graph (Complete Binary Tree):
1
/ \
2 3
/ \ / \
4 5 6 7
BFS Queue Max Size: 4 (last level)
DFS Stack Max Size: 3 (tree height)BFS: O(w) - w is the maximum width of the graph
DFS: O(h) - h is the maximum depth of the graph
Memory Comparison
| Graph Shape | BFS Memory | DFS Memory | Favorable |
|---|---|---|---|
| Complete Binary Tree (height h) | O(2^h) | O(h) | DFS |
| Linear (1→2→3→…→n) | O(1) | O(n) | BFS |
| General Graph | O(V) | O(V) | Similar |
The asymptotic numbers hide a practical difference: where the memory lives. BFS’s queue is on the heap and can grow as large as available memory. Recursive DFS uses the call stack, which is small and fixed, typically 8 MB on Linux and 1 MB by default on Windows. A DFS over a path-shaped graph or a large grid can recurse hundreds of thousands of levels deep; in C++ that ends in a segmentation fault (or Stack overflow on Windows) with no useful message, and in Python in RecursionError: maximum recursion depth exceeded after about 1000 levels. “DFS uses O(h) memory” is only reassuring when h is small.
Selection by Problem Type
When to Use BFS
- Shortest Path (unweighted graph)
// Minimum moves to escape maze
int shortestPath(int start, int end) {
queue<pair<int,int>> q; // {vertex, distance}
q.push({start, 0});
visited[start] = true;
while (!q.empty()) {
auto [u, dist] = q.front();
q.pop();
if (u == end) return dist; // Shortest distance guaranteed
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push({v, dist + 1});
}
}
}
return -1;
}- Level Order Traversal
// Print tree by level
void levelOrder(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
cout << "\n"; // Level separator
}
}When to Use DFS
- Path Existence
// Check if path exists (shortest path not needed)
bool hasPath(int start, int end) {
if (start == end) return true;
visited[start] = true;
for (int v : adj[start]) {
if (!visited[v] && hasPath(v, end)) {
return true;
}
}
return false;
}- Cycle Detection
bool hasCycle(int u, int parent) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
if (hasCycle(v, u)) return true;
} else if (v != parent) {
return true; // Cycle found
}
}
return false;
}This version is for undirected graphs, where every edge appears twice in the adjacency list and the edge back to parent must be ignored. Two things break it. With parallel edges between the same pair of vertices, skipping by parent vertex hides a real two-edge cycle; skipping by edge index fixes that. And on a directed graph it reports false cycles: in 1→2, 1→3, 3→2, vertex 2 is already visited when reached from 3, but there is no cycle. Directed graphs need three states (unvisited, on the current recursion path, finished), and only an edge to a vertex that is on the current path is a cycle.
3. Topological Sort
void topologicalSort(int u) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
topologicalSort(v);
}
}
result.push_back(u); // Post-order
}A vertex is appended only after all its descendants, so result holds the vertices in reverse topological order; call this for every unvisited vertex and then reverse(result.begin(), result.end()). This version also silently produces an ordering for a graph that has a cycle, where no valid order exists. Combining it with the three-state cycle check, or using BFS-based Kahn’s algorithm (repeatedly remove vertices with in-degree 0; if some vertices are never removed, there is a cycle), handles that case. Kahn’s algorithm is also iterative, which avoids the recursion-depth problem on long dependency chains.
Implementation Code
BFS Template
#include <queue>
#include <vector>
void BFS(int start) {
queue<int> q;
vector<bool> visited(n, false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
// Process
process(u);
// Adjacent vertices
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}DFS Template (Recursive)
void DFS(int u, vector<bool>& visited) {
visited[u] = true;
// Process
process(u);
// Adjacent vertices
for (int v : adj[u]) {
if (!visited[v]) {
DFS(v, visited);
}
}
}DFS Template (Iterative)
#include <stack>
void DFS_iterative(int start) {
stack<int> stk;
vector<bool> visited(n, false);
stk.push(start);
while (!stk.empty()) {
int u = stk.top();
stk.pop();
if (visited[u]) continue;
visited[u] = true;
// Process
process(u);
// Adjacent vertices (push in reverse order for same order as recursion)
for (int i = (int)adj[u].size() - 1; i >= 0; i--) {
int v = adj[u][i];
if (!visited[v]) {
stk.push(v);
}
}
}
}The iterative version is the safe choice for deep graphs, but it is not a drop-in replacement for the recursive one. It marks vertices when they are popped, so the same vertex can be on the stack several times and the stack can hold O(E) entries; the if (visited[u]) continue; line discards the duplicates. And it only gives you a pre-order visit. Algorithms that need to do something when a vertex is finished (topological sort, the three-state cycle check, Tarjan’s SCC) need the stack to remember where each vertex was in its adjacency list, typically by pushing (vertex, next_index) pairs. The (int) cast in the loop matters too: adj[u].size() - 1 is computed as an unsigned size_t, and without the cast an empty adjacency list would produce a huge value before the conversion.
Practical Examples
Example 1: Maze Escape (BFS)
// Shortest path → BFS
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int shortestPath(vector<vector<int>>& maze) {
int n = maze.size(), m = maze[0].size();
queue<tuple<int,int,int>> q; // {x, y, distance}
vector<vector<bool>> visited(n, vector<bool>(m, false));
q.push({0, 0, 0});
visited[0][0] = true;
while (!q.empty()) {
auto [x, y, dist] = q.front();
q.pop();
if (x == n-1 && y == m-1) return dist; // Arrived
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
!visited[nx][ny] && maze[nx][ny] == 0) {
visited[nx][ny] = true;
q.push({nx, ny, dist + 1});
}
}
}
return -1; // No path
}Storing the distance in the queue entry works, but a separate dist grid (initialized to -1, which doubles as the visited marker) is often more useful: after the BFS finishes, it holds the shortest distance from the start to every cell, which many problems need. For several starting points at once, such as “distance from the nearest fire”, push all sources with distance 0 before the loop (multi-source BFS) instead of running one BFS per source. When moves have costs 0 and 1 only, a deque with 0-cost moves pushed to the front (0-1 BFS) still runs in O(V + E); for arbitrary weights, use Dijkstra.
Example 2: Number of Islands (DFS)
// Number of connected components → DFS
void DFS(vector<vector<int>>& grid, int x, int y) {
int n = grid.size(), m = grid[0].size();
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
return;
}
grid[x][y] = 0; // Mark as visited
// Explore four directions
DFS(grid, x+1, y);
DFS(grid, x-1, y);
DFS(grid, x, y+1);
DFS(grid, x, y-1);
}
int numIslands(vector<vector<int>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
DFS(grid, i, j);
count++;
}
}
}
return count;
}This is the textbook DFS example and also the one where recursion most often fails in practice. A grid that is entirely land, say 1000 × 1000, makes the recursion snake through every cell, a depth of up to a million calls, which overflows the default stack. It passes small tests and crashes on the largest one. Counting components does not depend on visit order at all, so the same function written with BFS (or an explicit stack) is equally correct and has no depth limit. I use recursive flood fill only when the grid is known to be small; otherwise BFS is the default for grid components. Also note that this version marks cells by overwriting grid with 0, which is convenient but destroys the input; use a separate visited array when the caller still needs the grid.
Selection Criteria Summary
Flowchart
graph TD
A[Graph Traversal Problem] --> B{Shortest Path?}
B -->|Yes| C[BFS]
B -->|No| D{Explore All Paths?}
D -->|Yes| E[DFS]
D -->|No| F{Memory Constraint?}
F -->|Wide Graph| E
F -->|Deep Graph| C
Selection Table by Problem Type
| Problem Type | Algorithm | Reason |
|---|---|---|
| Shortest Path (unweighted) | BFS | Level order guarantee |
| Shortest Path (weighted) | Dijkstra | BFS variant |
| Path Existence | DFS | Memory efficient |
| Find All Paths | DFS | Backtracking |
| Cycle Detection | DFS | Use recursion stack |
| Topological Sort | DFS | Post-order |
| Number of Connected Components | DFS | Simple implementation |
| Bipartite Graph Check | BFS | Level distinction |
Conclusion
The key points when choosing between BFS and DFS:
- If you need shortest path (unweighted) → BFS is correct.
- If reachability or structural exploration is central → DFS is often easier to handle.
- For memory, queue (BFS) and stack (DFS) burdens differ depending on whether the graph is wide or deep, so always check constraints.
- For implementation convenience, match it to the problem type (backtracking uses DFS, etc.). Summary: Both have the same time O(V+E), but if shortest distance is the answer condition, prioritize BFS.
FAQ
Q1. Does BFS always guarantee the shortest path? Only in unweighted graphs. For weighted graphs, use Dijkstra.
Q2. Is DFS only implemented with recursion? It can also be implemented with iteration using a stack. Recursion is simpler but watch for stack overflow.
Q3. Which one to use for problems where both work? Choose the one that’s easier to implement; the time complexity is the same. The exception is depth: if the recursion could go tens of thousands of levels deep, prefer BFS or an iterative DFS.
Related Articles
- Graph Representation: Adjacency List vs Matrix
- BFS vs DFS: Choosing a Graph Traversal for Shortest Paths, Components and Cycles