DSA · Patterns, not puzzles
How does breadth-first search work?
Short answer
Breadth-first search explores a graph level by level using a queue, marking nodes as visited when they are enqueued. It finds the shortest path in an unweighted graph in O(V + E) time.
BFS starts at a source, visits all neighbours at distance one, then all nodes at distance two, and so on. The queue preserves that order. Marking a node when it is enqueued, rather than when it is dequeued, prevents duplicates from entering the queue.
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
let head = 0;
const order = [];
while (head < queue.length) {
const node = queue[head];
head += 1;
order.push(node);
for (const next of graph.get(node) || []) {
if (!visited.has(next)) {
visited.add(next);
queue.push(next);
}
}
}
return order;
}Why BFS finds shortest paths
- Nodes are processed in nondecreasing distance from the source
- The first time a node is reached, it is reached by a shortest path
- This holds for unweighted edges; weighted graphs need Dijkstra
- Time is O(V + E) with an adjacency list
- Space is O(V) for the queue and visited set
function shortestDistances(graph, start) {
const distances = new Map([[start, 0]]);
const queue = [start];
let head = 0;
while (head < queue.length) {
const node = queue[head];
head += 1;
for (const next of graph.get(node) || []) {
if (!distances.has(next)) {
distances.set(next, distances.get(node) + 1);
queue.push(next);
}
}
}
return distances;
}Follow-ups you should expect
Interviewers use these to check whether the first answer was understanding or memorisation.
- 1Why mark a node as visited when enqueuing rather than dequeuing?
- 2When does BFS not find the shortest path?
- 3How would you reconstruct the path, not just the distance?
- 4How does BFS differ from level order traversal of a tree?
Say it in the interview
BFS uses a queue to explore nodes in increasing distance from the start, and I mark a node visited when I enqueue it so it cannot be added twice. Because nodes are processed level by level, the first time I reach a node is the shortest unweighted path. I keep a parent map if I need to reconstruct the path, and for weighted graphs I switch to Dijkstra.
Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.
Related questions
Reading is step one
Now say it out loud.
Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.