HomeConceptsComputer ScienceAlgorithms and Search

Computer Science · Algorithms and Search

Breadth-First Search and Layered Frontiers

Simulation loading

Open Model Lab is preparing the live lab, controls, and graph surface for this concept.

Wrap-up

What you learned

Recommended next: Open concept testCheck whether the core ideas are ready without leaving this concept.
Read next: Depth-First Search and Backtracking PathsContrast queue order with stack order

Key takeaway

BFS fills the first frontier with same-depth neighbors before it goes deeper.
The queue frontier clears older discoveries first, which is what makes the search layered.
On an unweighted graph, BFS layers line up with fewest-edge distance from the start.

Common misconception

Breadth-first search just means moving around the page in a wide-looking pattern.

The drawing can be misleading. What matters is queue order: the oldest discovered node is expanded next.

Read the queue frontier and graph layers together

Keep this idea moving

Open the next concept, route, or track only when you want the current model to widen into a larger branch.

Compare a branch-first frontier on the same graphAlgorithms and Search

Depth-First Search and Backtracking Paths

Keep the stack frontier, current depth, and branch order visible together so depth-first search feels like disciplined backtracking instead of random wandering.

See how cycles and repeat skips change the bookkeepingAlgorithms and Search

Frontier and Visited State on Graphs

Use one cyclic graph to see which nodes are waiting, which are finished, and why repeat edges are skipped instead of reopening loops.

Next in Graph neighborhoods and adjacencyAlgorithms and Search

Graph Representation and Adjacency Intuition

Keep one live graph, one local neighborhood, and one frontier cue visible together so graph structure feels readable before traversal rules get formal.

Stay with this concept

Review, test, or free-play here when you want one more same-concept pass.

More practice optionsReview on the bench · Worked examples

Practice optionReview on the benchReplay the guided setup with the key controls and graphs in sight.
Practice optionWorked examplesCompare against solved walkthroughs after you try the setup yourself.
Practice optionFree play on the benchExperiment freely with the live controls before moving to another concept.

Reference and support

Use these calmer sections when you want a fuller explanation, examples, or accessibility support after the guided flow.

Return here when you want the slower reference pass.

Open reference and support

Equation snapshotLayer depth rule · Queue frontier updateShow 2 equations

Layer depth rule
$d (u) = d (v) + 1$
A newly discovered neighbor is one edge deeper than the node that found it.
Queue frontier update
$Q_{n e x t} = Q ∖ {v_{f r o n t}} \cup N_{n e w} (v_{f r o n t})$
BFS removes the oldest frontier node first, then adds its newly discovered neighbors to the back of the queue.

Why it behaves this way

Explanation

Breadth-first search explores an unweighted graph in layers. From the start node, it first reaches nodes one edge away, then nodes two edges away, and so on.

That layered pattern comes from the queue frontier. The oldest discovered node is expanded next, so shallow discoveries stay ahead of later deeper ones. On this bench, keep the graph, frontier cue, and depth history together so the rule stays visible.

Key ideas

01Breadth-first search reaches nodes in increasing fewest-edge distance from the start.

02The queue frontier expands the oldest waiting node first.

03The frontier can widen before it shrinks because one shallow node may discover several new neighbors.

Worked examples

Open examples when you want to see the same idea walked through step by step.

Frozen walkthrough

Step through the frozen example

Frozen walkthrough

Use the graph, frontier cue, and depth picture together to read what BFS should do first.

Supporter unlocks saved study tools, exact-state sharing, and the richer review surfaces that support this guided flow.

View plans

Frozen valuesUsing frozen parameters

Starting from A on the layered campus graph, which nodes should BFS settle before it goes deeper?

G

Graph layout

Layered campus

s

Start node

Q

Traversal mode

B then C

1. Read the first frontier

Starting from A, the first neighbors B and C become the first queue frontier.

2. Keep the queue order honest

Because BFS uses a queue frontier, B should leave the frontier before the later discovery C.

3. Connect queue order to layer depth

That oldest-first rule makes the search finish the shallow layer before it moves into deeper nodes like D, E, F, and H.

Layer-order summary

From A, BFS settles the B/C layer before it pushes deeper.

The queue frontier is what turns a graph traversal into a layered search rather than a branch-first dive.

Quick test

Loading saved test state.

Bench tools and share links

Keep stable concept links and exact-state sharing tucked away until you actually need to relaunch or share the bench.

Try this setup

Jump to a named bench state or copy the one you are looking at now. Shared links reopen the same controls, graph, overlays, and compare context.

Current bench

Layered campus BFS preset

This bench is currently showing one of the concept's authored presets.

Open default bench

Featured setups

Layered campus BFS

Use a clean graph where BFS finishes one shallow layer before moving to the next.

Hub and detours BFS

Start from the center so one shallow node makes the frontier widen before it narrows again.

Saved setups

Saved setups are a Supporter study tool. Stable concept links still work for everyone.

Checking saved setup access

Open Model Lab is resolving whether this bench can save locally, sync to an account, or open Supporter-only compare tools.

Copy current setup

Exact-state sharing is part of Supporter. Stable concept and section links still stay available.

Stable links

Progress and next steps

Keep progress signals, starter-track handoffs, and review prompts available without letting them compete with the live lesson flow.

Progress

Loading progress

Loading saved concept progress for this browser or synced account before showing completion status.

Starter track

Step 4 of 6

Algorithms and Search Foundations

Breadth-First Search and Layered Frontiers appears later in this track, so it is cleaner to start from the beginning first.

Previous step: Graph Representation and Adjacency Intuition

Start from track beginning