Middle · Algorithms
BFS and shortest unweighted paths
How do you find the fewest edges between two nodes?
Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.
ALGORITHM LAB · STEP THROUGH THE INVARIANT
0→[1, 2]; 1→[3]; 2→[3, 4]; 3→[]; 4→[]
Discover start
Mark on enqueue to avoid duplicate queue entries.
Computed traces for these inputs. Indexes identify cell positions; active cells are labeled as well as highlighted. Compare a boundary case using the scenario selector. No code is sent to a server.
// adj contains integer node IDs; all edges have unit cost.
func Distances(adj [][]int, start int) []int {
d := make([]int, len(adj))
for i := range d {
d[i] = -1
}
d[start] = 0
q := []int{start}
for head := 0; head < len(q); head++ {
v := q[head]
for _, w := range adj[v] {
if d[w] != -1 {
continue
}
d[w] = d[v] + 1
q = append(q, w)
}
}
return d
}Reveal a strong answer
Use a FIFO queue and mark a node visited when enqueuing it, not after dequeue. This prevents many parents from enqueueing the same node repeatedly. Set each newly discovered distance to parent distance+1.
BFS explores by increasing edge count, so the first discovery gives a shortest path in an unweighted graph. Store predecessor links to reconstruct the path; distance alone does not describe the route.
Disconnected nodes remain unreachable. A directed graph only permits listed outgoing edges. In Go, a head index avoids repeatedly shifting the queue; clear references or release the queue when retaining a long-lived backing array matters.
Common trap
BFS is not a shortest-cost algorithm when edges have different weights.
Complexity & use
O(V+E) time and O(V) extra storage. Useful for dependency reachability and shortest hop count.
Try it
For A→B,C; B→D; C→D,E, find distance and one path from A to E.
Worked solution
Enqueue A, then B and C at distance1. B discovers D at2; C skips already discovered D and discovers E at2. Predecessors reconstruct A,C,E. Test a cycle and an unreachable node.
Change the constraint
How would a multi-source BFS model the nearest replica or facility?
How did you do?
Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.
Not marked. Progress stays on this browser, separate from course completion.
Primary references
Checked 2026-10-20. Use documentation for your pinned runtime, driver and tool version.