Breadth-first search fans out in layers, visiting everything one step away before anything two steps away. You keep a queue of vertices to process and a visited set so you never revisit. Start by marking the source visited and putting it in the queue.
Then repeat until the queue empties:
Remove the front vertex
Look at each of its neighbors
For any unvisited neighbor, mark it visited and add it to the back
Because the queue is first-in first-out, closer vertices always come out first. That is what produces the ring-by-ring order. Each vertex enters the queue once and each edge is examined once, so the cost is O(V + E).
This layered order is exactly why BFS finds the fewest-edge path in an unweighted graph. The first time you reach a vertex, you reached it by the shortest number of hops.
Rewriting in plainer words…
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Start at the source, A. Mark it visited, which means we have seen it, and put it in the queue of vertices waiting their turn.
1 / 9← → keys
The queue is first in, first out, so vertices one hop away come out before any vertex two hops away. That is why BFS finds the path with the fewest edges.
Saved in this browser - sign in to keep your review list.
How should your speech become text?
Listening… your words appear above as you speak - tap Stop when you're done.
Recording · cr - tap Stop & transcribe when you're done.
Transcribing with AI…
Voice:
Keep going - a few more words and AI can grade it.
Interview lens
How interviewers actually use this question
Likely follow-ups
Why mark a vertex visited when it enters the queue rather than when it leaves?Marking on removal lets the same vertex be queued many times. Marking on entry keeps each vertex in the queue once, which the O(V + E) bound relies on.
BFS explores a graph in layers, visiting everything one edge from the start before anything two edges away.
It keeps a queue of vertices to process and a visited set, and it starts by marking the source visited and enqueuing it.
Then, until the queue is empty, I take the front vertex and mark and enqueue every neighbor that isn't visited yet.
The queue is first-in first-out, so closer vertices always come out before farther ones, and that gives the ring-by-ring order.
Each vertex enters the queue once and each adjacency list gets scanned once, so it's O(V + E).
That layering is why BFS finds the fewest-edge path in an unweighted graph, but with weighted edges fewest hops isn't cheapest, so I'd use Dijkstra.
Weak answers to avoid
Leaves out the visited setOn a graph with a cycle the search loops forever or reprocesses vertices. A tree can get away without one and a graph cannot, so name it up front.
Marks vertices visited only when dequeuedThe same vertex then gets enqueued once for every neighbor that sees it, which adds duplicate work. Mark it on enqueue so each vertex enters the queue once.
Says BFS finds shortest paths in any graphThat only holds when every edge counts the same. Say it's for unweighted graphs and name Dijkstra for weighted ones, or expect the interviewer to push there.
Recites the loop but never says why it's layeredThe point is the chain from first-in first-out to ring-by-ring order to fewest hops. Without it, the steps sound memorized.
Interview lens
Likely follow-ups, what you can say, and the weak answers to avoid.
