Trace Breadth-First Layers
Expand all current-layer vertices before moving to the next layer, marking discoveries once.
About 22 minutes, plus any extended practice
Supplied materials
- Paper and pencil; answers may also be spoken or typed.
- All cases, labels, numbers and rules are supplied on this page. No real account, private information or purchase is needed.
Learn the idea
Breadth-first exploration of an unweighted graph discovers vertices by hop distance from a start. Marking a vertex when discovered prevents adding it repeatedly. A queue holds discovered work waiting to be expanded. The supplied model asks for layers, not weighted shortest distance.
Expand all current-layer vertices before moving to the next layer, marking discoveries once. Fewest hops need not mean minimum travel time when edges have different costs.
Use this supplied case: Vertex A. Undirected edges A-B,A-C,B-D,C-E,D-F. Start A. Which layer contains the requested vertex? The task is to connect the given information to the computing idea. Write a short evidence trail so another learner can reproduce your choice. The simplified case describes the stated model, not every real system.
- Represent the supplied worked case with a labeled drawing, table or short trace.
- Expand all current-layer vertices before moving to the next layer, marking discoveries once.
- Explain why the worked answer fits and why one alternative does not.
- Try the new check and practice cases; revisit the stated rule if your evidence does not match.
See the method in action
The distinct undirected edges are J–K, J–L, K–M, L–N and M–P. Begin layer 0={J}, queue [J], visited {J}. Expanding J discovers K,L: layer 1, queue [K,L]. Expanding K discovers M and expanding L discovers N: layer 2, queue [M,N]. Expanding M discovers P: layer 3; N adds no new vertex. Mark vertices when first discovered to avoid repeated reverse-edge visits. These are unweighted hop layers, not weighted travel times.
Check your reasoning
Your answer is temporary and is not saved to an account. Download your current answer before leaving or reloading. Written work on paper or in another app stays in your own file.
Helpful tips
- Expand all current-layer vertices before moving to the next layer, marking discoveries once.
- Fewest hops need not mean minimum travel time when edges have different costs.
See the answer and explanation
Layer 1
The undirected edges are A–B, A–C, B–D, C–E, and D–F. Start with layer 0={A}, queue [A], and visited {A}. Remove A and discover B and C: queue [B,C], layer 1={B,C}. Remove B, discover D, then remove C and discover E: queue [D,E], layer 2={D,E}. Remove D and discover F; E adds no new vertex. Layer 3={F}. Mark vertices when discovered so reverse edges do not re-add A or B. These are unweighted hop layers, not weighted travel times. The requested case is: Vertex B. Undirected edges A-B,A-C,B-D,C-E,D-F. Start A. Which layer contains the requested vertex? Its answer is Layer 1.
Take it further
New edges S-A, S-B, A-C, B-D, C-E. BFS from S gives layer 0 S, layer 1 A/B, layer 2 C/D, layer 3 E. A visited set prevents repeated discoveries.
Nothing here is saved to an account or sent to a teacher. The answer download includes your current choice and any checked feedback. It does not include choices from the separate More practice section. Download that section separately.
More practice: try new cases
Choose an answer for each problem. Explain your method on paper, then use the feedback to decide what to revisit.
Your choices are temporary. Feedback appears after you check all the answers.
Nothing here is saved to an account or sent to a teacher. Keep your own notes or download them before leaving. The score describes these questions; it does not certify subject mastery.
Check the subject sources
These LifeStarter passages, scenarios and exercises are authored for this Academy with AI assistance and review. External resources keep their publishers’ terms. A grade label suggests a starting level; it does not establish alignment with your school’s complete requirements.