LearnThatStack Ace your next interview
Graphs · question
Question 6 of 60

How does breadth-first search explore a graph, step by step

beginner
← All Graphs questions
Re-explain

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.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·
What should the new diagram focus on?
How well did you know this?
AI:

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

Likely follow-ups, what you can say, and the weak answers to avoid.

Sign in free to open it Free account - the lens opens as soon as you're back.

Want a quick review of the fundamentals? See the Graphs cheatsheet.

← Back to all Graphs questions
Pro · $10/mo

51 of 60 Graphs answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

  • Full answers + code
  • AI explanations, simpler or deeper
  • 1,000 AI credits / month
  • Cancel anytime