A strong answer
BFS starts with the source in a queue at distance 0. It repeatedly dequeues a vertex in queue order and, for each unvisited neighbor, marks it, gives it the current distance plus one, and enqueues it. It runs in O(V + E).
The key property is that the queue holds vertices in nondecreasing order of distance, and at any moment it contains at most two consecutive distances, d and d + 1. That holds at the start, and each dequeue of a distance-d vertex only appends vertices at distance d + 1 to the back. So all vertices at distance d are processed before any at d + 1.
Now suppose a vertex v is first discovered from u, so it gets distance dist(u) + 1. If there were a shorter path to v, its second-to-last vertex w would have dist(w) < dist(u), so w would have been dequeued before u and would have discovered v first. Contradiction. So the first discovery gives a shortest distance, and later discoveries can be ignored. Storing each vertex's parent at discovery lets you walk back from the target to rebuild a shortest path.
The argument relies on every edge counting as 1. With weights, a path with more edges can be shorter in total, and BFS gives wrong answers; Dijkstra's algorithm replaces the queue with a priority queue ordered by distance. When weights are only 0 or 1, 0-1 BFS keeps a deque, putting 0-weight neighbors at the front, and still runs in O(V + E).
What the interviewer is listening for
- The algorithm, with visited marking on enqueue.
- An actual argument based on the queue's order, not just "it explores level by level".
- Path reconstruction, and the limits with weighted edges.
Common mistakes
- Marking on dequeue, which duplicates work.
- Using BFS on weighted graphs.
- Forgetting that the guarantee is about the number of edges.