What is the difference between BFS and DFS, and when would you use each?
BFS (breadth-first search) explores a graph level by level using a queue, so it finds the shortest path in an unweighted graph. DFS (depth-first search) goes as deep as possible along one path before backtracking, using a stack or recursion, and suits cycle detection, topological sort and exploring all paths. Both take O(V + E) time.
Explain it simply
Imagine you have lost your phone somewhere in a large hostel.
- BFS: you first check every room on your own floor, then every room one floor away, then two floors away. You spread out in rings. If the phone is close, you find it fast, and you always find it via the shortest route.
- DFS: you pick one corridor and keep walking to its very end, checking every room down that path, and only then come back to try the next corridor. You go deep first.
BFS uses a queue (first in, first out), like a ticket counter line. DFS uses a stack (last in, first out), or simply recursion.
Line by line
// Graph as an adjacency list
const graph = {
A: ["B", "C"],
B: ["D", "E"],
C: ["F"],
D: [],
E: ["F"],
F: [],
};
function bfs(start) {
const visited = new Set([start]);
const queue = [start];
const order = [];
while (queue.length > 0) {
const node = queue.shift(); // take from the front
order.push(node);
for (const next of graph[node]) {
if (!visited.has(next)) {
visited.add(next); // mark when added, so it is queued only once
queue.push(next);
}
}
}
return order;
}
function dfs(node, visited = new Set(), order = []) {
visited.add(node);
order.push(node);
for (const next of graph[node]) {
if (!visited.has(next)) {
dfs(next, visited, order); // go deep before trying the next neighbour
}
}
return order;
}
console.log(bfs("A").join(" ")); // Output: A B C D E F
console.log(dfs("A").join(" ")); // Output: A B D E F C- BFS visits A, then its neighbours B and C, then the next level D, E, F.
- DFS goes A → B → D (dead end), back to B → E → F, then back up to A → C (F is already visited).
How it works
| BFS | DFS | |
|---|---|---|
| Data structure | Queue | Stack or recursion |
| Order | Level by level | One path to the end, then backtrack |
| Shortest path (unweighted) | Yes, guaranteed | No |
| Memory | Can hold a whole level, which is wide for bushy graphs | Holds one path, which is long for deep graphs |
| Typical uses | Shortest path, nearest neighbour, level-order traversal | Cycle detection, topological sort, connected components, backtracking |
On a tree, DFS gives the familiar pre-order, in-order and post-order traversals, and BFS gives level-order traversal.
Complexity
| Time | Extra space | |
|---|---|---|
| BFS | O(V + E) | O(V) for the queue and visited set |
| DFS | O(V + E) | O(V) for the visited set and the recursion stack |
V is the number of vertices and E the number of edges, with an adjacency list. Each vertex is visited once and each edge is looked at once (twice for undirected graphs).
Real-world use
- BFS: "people you may know" at 2nd and 3rd degree on LinkedIn, the minimum number of moves in a puzzle, finding the nearest open seat in a grid.
- DFS: finding the order to build modules with dependencies (topological sort), solving mazes and Sudoku by backtracking, checking whether a network is fully connected.
Common mistakes
- Not tracking visited nodes in a graph with cycles, which loops forever.
- Marking visited when you remove from the queue instead of when you add. The same node can then be queued many times.
- Using
array.shift()on huge inputs. In JavaScript it is O(n) per call. For large graphs, keep a head index instead of shifting, or use a proper queue. - Deep recursion in DFS on a graph with lakhs of nodes in a long chain, which overflows the call stack. Switch to an explicit stack.
- Claiming DFS finds shortest paths. It does not, even in unweighted graphs.
What to say in the interview
"BFS explores level by level using a queue, so the first time it reaches a node is through the fewest edges. That makes it the right choice for shortest paths in unweighted graphs. DFS goes deep along one branch before backtracking, using recursion or a stack, and I use it for cycle detection, topological sorting, counting connected components and backtracking problems. Both are O(V plus E) time with an adjacency list. In both I keep a visited set so cycles do not cause infinite loops."
Follow-up questions
- How would you find the shortest path in a grid with obstacles?
- How do you detect a cycle in a directed graph using DFS?
- What would you use for shortest paths when edges have weights?
- How do you write DFS iteratively?
Go deeper
Read these once the basics above feel easy.
Shortest path with BFS: store a distance for each node. Set the start's distance to 0, and when you add a neighbour to the queue, set its distance to the current node's distance plus 1. This works because BFS finishes all nodes at distance d before any node at distance d + 1. With weighted edges this breaks; use Dijkstra's algorithm (non-negative weights) instead.
Cycle detection in a directed graph with DFS: keep three states per node: unvisited, in progress (on the current recursion path) and done. Reaching an "in progress" node again means you found a back edge, which is a cycle. A plain visited set is not enough in directed graphs, because reaching a "done" node through a different path is not a cycle.