Breadth-First Search

Breadth-first search explores a graph level by level: first every neighbour of the start, then their neighbours, and so on — using a queue.

Start at A

A
B
C
D
E
F

Queue (front → back)

A

Visit order: —

  • Current
  • In the queue
  • Visited
  • Edge being checked

BFS explores level by level, using a queue (first in, first out). A goes in first.

Step 1 / 26
Visited
0
In queue
1
queue = [start]; mark start seen
while queue not empty:
  node = queue.removeFirst()
  for each neighbour of node:
    if not seen: mark seen; queue.add(neighbour)
Start at

What's happening?

  1. Put the start node in a queue and mark it seen.
  2. Take the node at the front of the queue and visit it.
  3. Add each of its neighbours that has not been seen to the back of the queue; repeat until the queue is empty.

Complexity

Time
O(V + E) — every node and edge once
Space
O(V) for the queue and the seen set

Where you'll meet it

Shortest paths when every step costs the same (fewest hops, fewest moves in a puzzle), "people you may know" (friends of friends), web crawlers and network broadcast.

Common mistake

Marking a node as seen only when it is visited instead of when it is queued — the same node then gets queued many times.

FAQ

Why does BFS find the shortest path?

It reaches every node at distance 1 before any at distance 2, so the first time it reaches a node is by the fewest edges.

BFS vs DFS?

BFS uses a queue and spreads out evenly; DFS uses a stack (or recursion) and goes deep first. Compare them on the same graph here.

Does BFS work with weighted edges?

Not for shortest paths — use Dijkstra when edges have different costs.