When should you use BFS versus DFS when traversing a graph?
BFS (queue): shortest path in an unweighted graph, level-order, 'closest match'. DFS (stack/recursion): connectivity, cycle detection, topological sort, path enumeration, backtracking. BFS uses more memory (frontier width); DFS uses less but can recurse deep. Both must track visited.
Both visit every reachable node in O(V + E), but the order matters — and so does the memory profile.
BFS — breadth-first
Uses a queue. Explores all neighbors at distance d before distance d+1.
Use BFS when:
- You need the shortest path in an unweighted graph (or fewest edges).
- You need level-order: nearest match first, closest neighbor, friends-of-friends at depth k.
- Memory permits storing the frontier (can be wide on dense graphs).
function bfs(start, adj) {
const visited = new Set([start]);
const queue = [[start, 0]];
while (queue.length) {
const [node, dist] = queue.shift();
for (const n of adj[node] || []) {
if (!visited.has(n)) {
visited.add(n);
queue.push([n, dist + 1]);
}
}
}
}(For hot loops, use an index-based or linked-list queue — shift is O(n).)
DFS — depth-first
Uses a stack (or recursion). Dives along one branch before backtracking.
Use DFS when:
- Connectivity / connected components — does a path exist? Who's reachable?
- Cycle detection in directed/undirected graphs.
- Topological sort (DFS post-order on a DAG).
- Path enumeration / backtracking — N-Queens, word search, Sudoku.
- Memory is tight — DFS holds only the current path.
function dfs(node, adj, visited = new Set()) {
if (visited.has(node)) return;
visited.add(node);
for (const n of adj[node] || []) dfs(n, adj, visited);
}The decision
| Need | Pick |
|---|---|
| Shortest path / fewest hops | BFS |
| Closest match / nearest first | BFS |
| All paths / backtracking | DFS |
| Cycle detection | DFS |
| Topological sort | DFS |
| Components / reachability | Either |
Gotchas
- Always track visited — graphs may have cycles.
- Weighted graphs — neither BFS nor plain DFS gives shortest path; use Dijkstra.
- Very deep graphs — recursive DFS can blow the stack; use iterative DFS.
Interview framing
"BFS for shortest path in unweighted graphs and level-order problems — it explores by distance from the source. DFS for connectivity, cycle detection, topological sort, and path enumeration — it's also lighter on memory because you only hold the current path. Both need a visited set. For weighted graphs, neither: you need Dijkstra."
Follow-up questions
- •Why does BFS find the shortest path in an unweighted graph?
- •How do you detect a cycle in a directed graph with DFS?
- •When does DFS recursion become a problem and how do you fix it?
Common mistakes
- •Forgetting the visited set on a cyclic graph → infinite loop.
- •Using BFS for weighted shortest path (need Dijkstra).
- •Using array.shift() in BFS on big graphs.
Performance considerations
- •Both O(V + E). BFS memory is the maximum frontier width (can be huge on dense graphs); DFS memory is the recursion / explicit stack depth.
Edge cases
- •Disconnected graphs — wrap traversal to cover all components.
- •Self-loops, duplicate edges, very wide branching factor (BFS memory).
Real-world examples
- •Friend-of-friend recommendations (BFS).
- •Build dependency / topological sort of a task graph (DFS).
- •Path-finding in a maze / grid (BFS for shortest path).