A girl and a robot thinking together

Think together · Start with a little story

The girl draws circles on the ground: first check everywhere you can reach in one step, then everywhere you can reach in two.

Lay out the process

Follow the steps, then explain them in your own words
  1. Layer 0Starting point
  2. Layer 1Reachable in one step
  3. Layer 2First reachable in two steps
  4. QueueKeep items in order

Breadth-first search expands outward layer by layer.

Put the starting point in a queue. After removing a node, add its newly discovered neighbors. Marking them when enqueued usually prevents the same node from being queued repeatedly.

Watch how the queue changes

Start at A. The row shows the queue from front to back.

Step 1 · Start at A
A

A has been discovered, and its distance is 0.

Step 2 · Remove A
BC

Enqueue and mark the undiscovered B and C. Their distance is 1.

Step 3 · Remove B
CD

D is enqueued at distance 2. C stays ahead of D in the queue.

Step 4 · Remove C
DE

E is enqueued at distance 2. The first layer has now been processed.

Step 5 · Remove D and E
Empty queue

There are no new undiscovered neighbors. This example visits A, B, C, D, E.

01What is BFS?

BFS (Breadth-First Search) starts at a point and expands outward one layer at a time.

StartLayer 1Layer 2Layer 3

02Why is it like a ripple?

Drop a stone into water: ripples reach nearby places before farther ones.

BFS also handles states closer to the start before states farther away.

03Why does BFS use a queue?

A queue is first-in, first-out.

The node discovered first is handled first, which ensures that closer layers are expanded sooner.

Discover a node→Add it to the back→Process nodes from the front

04The basic code structure

std::queue<int> q;
q.push(start);
visited[start] = true;

while (!q.empty()) {
    int u = q.front();
    q.pop();

    for (int v : graph[u]) {
        if (!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}

05Why mark visited when enqueuing?

If you wait until a node is removed from the queue, multiple predecessors may add the same node more than once.

06What can BFS do?

  • Traverse a tree level by level.
  • Find the fewest steps in an unweighted graph.
  • Find a shortest path through a maze.
  • Search for connectivity.
  • Solve multi-source expansion problems.

What have you learned?

  • BFS expands outward layer by layer according to distance.
  • BFS usually uses a queue.
  • Nodes discovered first are processed first.
  • Usually, mark a node visited when it is first discovered.
  • BFS is an important foundation for shortest paths in unweighted graphs.

Next: Finding the Shortest Path with BFS

Your turn to try

Why mark a node visited when you add it to the queue instead of waiting until you remove it?

Ready? Open to see the explanation

Marking it on discovery prevents multiple predecessors from adding the same node to the queue.