BEGINNER · 8 MIN · FREE LESSON
Breadth-first search
Explore one layer at a time.
Loading interactive lesson…
Next: Depth-first search →
BEGINNER · 8 MIN · FREE LESSON
Explore one layer at a time.
Loading interactive lesson…
Enter {"n":5,"edges":[[0,1,2],[1,2,3],[0,3,1],[3,4,2]],"directed":false,"start":0,"target":4}. Vertices are 0 through n−1.
Mark the start when adding it to the frontier.
Mark each reached vertex once and inspect its outgoing edges. BFS uses FIFO order and gives unweighted shortest-hop distance; DFS follows one branch with a recursive call stack.
Measured reads + comparisons, seed 42. Plotted sample sizes respect each lesson’s explicit input limits.
Keyboard: Space play/pause · ←/→ step · R restart · 1–5 speed. Reduced motion disables transitions.
A ripple reaches every nearby vertex before the next layer.
Explore complete distance layers. Edit the graph JSON to add a cycle, isolate a vertex or change an edge weight. Nodes are numbered from zero.
Predict the next frontier decision or edge operation before revealing it. Compare a connected graph with the same graph after removing an important edge.
O(V+E) time and O(V) traversal workspace. Every reached vertex enters the FIFO frontier exactly once, and its outgoing adjacency list is scanned once. Discovery layers give shortest hop distances. The counters count teaching operations; animation duration is not a CPU benchmark.
The four references show the core operation. Adjacency-list inputs use zero-based vertex indices. Weighted references use (neighbor,weight) pairs or explicit edge triples. Validate the graph assumptions before calling standalone code.
Use for unweighted shortest hops and level exploration.
Edge weights are ignored for hop distances; use Dijkstra or Bellman–Ford for weighted routes.
Check the graph assumptions, invariant and boundary conditions below.
MAKE IT STICK
Progress saves on this device and merges with your account after sign-in.
0 / 5000 · Saved on this device; synced when signed in.