BFS vs DFS — Graph Traversal Interview Questions
The Interview Question
What's the difference between BFS and DFS? When would you use each one?
Expert Answer
BFS (Breadth-First Search) explores all neighbors at the current depth before moving deeper. It uses a queue and visits nodes level by level. DFS (Depth-First Search) explores as far as possible along each branch before backtracking. It uses a stack (or recursion, which uses the call stack). The key distinction for interview problems: BFS guarantees the shortest path in unweighted graphs because it explores all nodes at distance k before any at distance k+1. DFS is better for problems that need to explore all paths, detect cycles, or search deep trees where the answer is far from the root. Memory-wise: BFS stores an entire level in the queue (O(branching_factor^depth)), while DFS stores a single path (O(depth)). For a wide, shallow graph, DFS uses less memory. For a narrow, deep graph, BFS uses less.
Key Points to Hit in Your Answer
- BFS = queue, level-by-level; DFS = stack/recursion, branch-by-branch
- BFS finds shortest path in unweighted graphs
- DFS is better for: cycle detection, topological sort, path finding in mazes
- BFS memory: O(w) where w is max width; DFS memory: O(h) where h is max depth
- Both visit every node once: O(V + E) time for adjacency list representation
- Topological sort uses DFS with post-order recording
Code Example
// BFS — shortest path in unweighted graph
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
const distance = { [start]: 0 };
while (queue.length > 0) {
const node = queue.shift();
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
distance[neighbor] = distance[node] + 1;
queue.push(neighbor);
}
}
}
return distance;
}
// DFS — detect cycle in directed graph
function hasCycle(graph) {
const WHITE = 0, GRAY = 1, BLACK = 2;
const color = {};
function dfs(node) {
color[node] = GRAY; // visiting
for (const neighbor of graph[node] || []) {
if (color[neighbor] === GRAY) return true; // back edge = cycle
if (color[neighbor] === WHITE && dfs(neighbor)) return true;
}
color[node] = BLACK; // done
return false;
}
return Object.keys(graph).some(n => !color[n] && dfs(n));
}What Interviewers Are Really Looking For
Know the data structure difference (queue vs. stack) and when each algorithm is appropriate. 'Shortest path in unweighted graph' → BFS immediately. 'Detect cycle' → DFS with coloring. Being able to implement both from memory is expected. Follow-up: 'How would you find shortest path in a weighted graph?' → Dijkstra's (BFS with priority queue).
Practice This Question with AI Grading
Reading about interview questions is a start — but practicing with real-time AI feedback is how you actually get better. Goliath Prep grades your answers instantly and tells you exactly what you're missing.
Start Practicing Free →