Explore a graph without getting trapped
How does a queue find shortest unweighted paths despite cycles?
Entering midway? Vertices are objects and edges connect pairs. A path follows adjacent vertices; its unweighted length is the number of edges.
Start with a concrete question
Six vertices include a cycle and a separate component unless the bridge is added.
Try the initial inputs, then write a prediction before changing one setting. All calculations run locally on your CPU.
Go directly to the experiment · Review prerequisite mathematics and return here
What do you expect?
Predict before calculating: How does a queue find shortest unweighted paths despite cycles?
Change one thing. Inspect what happens.
- Trace the queue from vertex 0.
- Find the unreachable component without a bridge.
- Add the bridge and recover a shortest path to 5.
- Explain why visited marking prevents repeated discovery around the cycle.
Your settingsMechanism
Calculation belowEvidence
Compare outcomes
Graph layout: shortest paths count edges, not geometric length
Horizontal: layout coordinate (not distance). Vertical: layout coordinate.
- 1. edge 0–1 (solid line)
- 2. edge 0–2 (dashed line)
- 3. edge 1–3 (dashed line)
- 4. edge 2–3 (dashed line)
- 5. edge 4–5 (dashed line)
- 6. vertex 0 (target) (points)
- 7. vertex 1 (points)
- 8. vertex 2 (points)
- 9. vertex 3 (points)
- 10. vertex 4 (points)
- 11. vertex 5 (points)
Axes use the displayed ranges.
Read plotted values as a table
| Series | layout coordinate (not distance) | layout coordinate |
|---|---|---|
| edge 0–1 | 0 | 1 |
| edge 0–1 | 1 | 2 |
| edge 0–2 | 0 | 1 |
| edge 0–2 | 1 | 0 |
| edge 1–3 | 1 | 2 |
| edge 1–3 | 2 | 1 |
| edge 2–3 | 1 | 0 |
| edge 2–3 | 2 | 1 |
| edge 4–5 | 3 | 1 |
| edge 4–5 | 4 | 1 |
| vertex 0 (target) | 0 | 1 |
| vertex 1 | 1 | 2 |
| vertex 2 | 1 | 0 |
| vertex 3 | 2 | 1 |
| vertex 4 | 3 | 1 |
| vertex 5 | 4 | 1 |
Follow the calculation
- Undirected edges: 0–1, 0–2, 1–3, 2–3, 4–5.
- Expand 0; queue=1, 2; distances=[0,1,1,unreached,unreached,unreached].
- Expand 1; queue=2, 3; distances=[0,1,1,2,unreached,unreached].
- Expand 2; queue=3; distances=[0,1,1,2,unreached,unreached].
- Expand 3; queue=empty; distances=[0,1,1,2,unreached,unreached].
- Shortest path: 0.
Breadth-first search explores by edge distance in an unweighted graph. Marking a vertex when it enters the queue prevents cycles from creating unbounded repeated work.
Captures keep your inputs, prediction and observation. Results are recalculated from those inputs. Resetting inputs keeps your captures and challenge history.
Explain the mechanism
Explore a graph without getting trapped
Six vertices include a cycle and a separate component unless the bridge is added.
Concepts to recall
Vertices are objects and edges connect pairs. A path follows adjacent vertices; its unweighted length is the number of edges.
Understand the mechanism
Vertices 0,1,2,3 form a cycle; 4 and 5 form a separate component.
With bridge 3–4, the path 0→1→3→4→5 uses four edges. The equally short route through 2 is resolved by stable neighbor ordering.
Breadth-first search discovers vertices by increasing edge distance. A queue differs from a stack; weighted shortest paths need a different method.
Symbols and calculation
distance(start)=0; when discovering neighbor v from u, distance(v)=distance(u)+1. Each undirected edge contributes two neighbor reads in a complete component traversal.
Worked example
Undirected edges: 0–1, 0–2, 1–3, 2–3, 4–5.
Expand 0; queue=1, 2; distances=[0,1,1,unreached,unreached,unreached].
Expand 1; queue=2, 3; distances=[0,1,1,2,unreached,unreached].
Expand 2; queue=3; distances=[0,1,1,2,unreached,unreached].
Expand 3; queue=empty; distances=[0,1,1,2,unreached,unreached].
Shortest path: 0.
Your investigation
Trace the queue from vertex 0.
Find the unreachable component without a bridge.
Add the bridge and recover a shortest path to 5.
Explain why visited marking prevents repeated discovery around the cycle.
Limits and interpretation
- These are bounded teaching models with explicit assumptions, not evidence of a real-world intervention.
Try a fresh case
A connected undirected graph has seven edges. A complete adjacency-list traversal reads each endpoint adjacency once. How many neighbor reads occur?
This is a public practice check. Retries support learning; matching a number does not certify independent proficiency.
Take the investigation further
Choose any extension. These are project prompts for you to carry out; they are not automatically assessed.
School investigation
Explain a fresh small numerical case with a diagram or table and an argument.
College investigation
Implement the method, test a boundary or counterexample, and justify its assumptions.
Workplace investigation
Use a small decision scenario, state units and constraints, and test how the recommendation changes.
Keep the evidence, choose your next step
Completion records your own decision that you have worked through this investigation. Practice checks and independent project evidence are separate.