VecDeque and breadth-first search

Walk a graph breadth-first from a starting node.

pub fn bfs_order(adj: Vec<Vec<usize>>, start: usize) -> Vec<usize>

adj[i] lists the neighbours of node i. Return the nodes in the order BFS visits them: start first, then all of its neighbours in the order they appear in adj[start], then their unvisited neighbours, and so on. Each node appears once.

Edge cases that are all real test cases:

• start out of range → empty Vec, not a panic.
• a neighbour index out of range → skip it, no panic.
• a self-loop → visited once.
• a disconnected graph → only the component containing start.

You must use a VecDeque. The harness cannot see which container you used, so this is on your honour — but read on for why it matters, because the alternative is both slower and, in the shape most people write, a different algorithm.

The compile error

The starter uses a Vec as the frontier and calls pop_front:

error[E0599]: no method named `pop_front` found for struct `Vec<usize>`
              in the current scope

There is no Vec::pop_front, and its absence is deliberate. A Vec is one contiguous block with the live elements at the front. pop from the back is O(1) — decrement the length. Removing from the front means shifting every remaining element down one, which is O(n). std will not give you a one-word name for an O(n) operation on a type where you would reasonably expect O(1), so if you want it you must spell it v.remove(0) and own the decision.

Write a BFS with v.remove(0) and you get the right answer in O(V·E) time instead of O(V+E). Write it with v.pop() — the O(1) one — and you get a DFS, silently, with no warning at all. That is what the “BFS and DFS differ” test case is for: adj = [[1,2],[3],[3],[]] visits [0,1,2,3] breadth-first and [0,2,3,1] depth-first. Both are respectable traversals. Only one is the one you asked for.

What a VecDeque is

A ring buffer: one allocation, plus a head index and a length. Pushing or popping at either end is O(1) amortised, because the “front” is wherever the head index currently points rather than the start of the buffer.

use std::collections::VecDeque;

let mut q = VecDeque::new();
q.push_back(x);        q.push_front(x);
q.pop_front();         q.pop_back();
q.front();             q.back();

A queue is push_back + pop_front. A stack is push_back + pop_back. Swapping one word between those two lines is the entire difference between BFS and DFS, which is worth pausing on: the algorithm lives in the data structure, not in the loop.

while let Some(node) = queue.pop_front() is the idiomatic loop. It is one operation instead of “check is_empty, then pop, then unwrap”, and it makes the “the queue drained” case impossible to forget.

The price of the ring: it is not a slice

Because the elements wrap around the end of the buffer, a VecDeque cannot hand you a &[T]. It gives you two of them:

let mut d: VecDeque<i32> = VecDeque::with_capacity(8);
for i in 0..6 { d.push_back(i); }
d.pop_front(); d.pop_front(); d.pop_front();
d.push_back(100); d.push_back(101); d.push_back(102);

d.as_slices()   // ([3, 4, 5, 100, 101], [102])

There is the ring, visible: five elements to the end of the buffer, then one that wrapped around to the beginning. iter() hides the seam and yields [3, 4, 5, 100, 101, 102] as you would hope, but anything that genuinely needs one contiguous slice — passing to a C function, a memcpy, a &[u8] write — has to call make_contiguous(), which rotates the elements in place (O(n), once) and then returns a single &mut [T].

This is a good, small lesson about abstraction: a type cannot always give you a view its representation does not have. Vec can hand out a slice because it is one. VecDeque cannot, and rather than lie or allocate behind your back it makes the seam part of the API.

::: question BFS needs a “have I seen this node?” check. Why vec![false; n] rather than a HashSet<usize>? Because the keys are dense small integers, and a Vec<bool> indexed by node is one byte per node with an O(1) array access and perfect cache behaviour — no hashing, no probing, no pointer chasing. For n nodes numbered 0..n, which is exactly what an adjacency-list-as-Vec<Vec<usize>> gives you, it is the right structure.

A HashSet earns its place when the node identifiers are sparse, large, or not integers at all — strings, UUIDs, coordinates. Then you cannot index an array by them without a mapping step, and the hash set is the mapping step.

This is the same judgement the container-choice article in this track is about: pick by the shape of the keys, not by the name of the operation. :::

One clippy note

The starter also walks the neighbour list by index:

for i in 0..adj[node].len() {
    let next = adj[node][i];

needless_range_loop exists for that shape. for &next in &adj[node] is shorter, has no bounds check per iteration, and cannot go out of range at all. Indexing in a loop is almost always a for over the collection wearing a disguise.

Remember the grade is compile + tests + clippy -D warnings.