VecDeque and breadth-first search

Breadth-first search (BFS) visits a graph in layers: first the starting node, then every node one edge away from it, then every node two edges away, and so on. In this exercise you return the order in which BFS visits the nodes.

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

The contract

The graph is an adjacency list. Nodes are numbered 0..adj.len(), and adj[i] lists the nodes that node i has an edge to. Edges are directed: 1 appearing in adj[0] does not imply that 0 appears in adj[1].

Visit the nodes like this:

1. Put start in a queue and mark it as seen.
2. Take the node at the front of the queue and append it to the output.
3. Go through that node's list in the order it is written. For each neighbour that is in range and not yet seen, mark it as seen and add it to the back of the queue.
4. Repeat from step 2 until the queue is empty.

Marking a node when it is added to the queue, rather than when it is taken out, is what makes each node appear at most once. With this rule and the list order fixed, there is exactly one correct output for every input.

These cases are all in the tests:

• start >= adj.len(), including an empty adj: return an empty Vec. Do not panic.
• A neighbour index >= adj.len(): ignore it. Do not panic.
• A self-loop (i listed in adj[i]), or a node that several other nodes point to: the node still appears once. (The same holds if a list names a neighbour twice.)
• A disconnected graph: return only the nodes reachable from start.

The result is printed as JSON in the form {"value": [0, 1, 2]}.

Use a VecDeque as the queue. The tests only see the output, so they cannot check which container you used. The sections below explain why a VecDeque is the right choice and what goes wrong with the two obvious Vec alternatives.

The compile error

The starter uses a Vec as the queue and calls pop_front, which Vec does not have:

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

A Vec stores its elements in one contiguous block, starting at the beginning of the block. Removing the last element with pop is O(1): the length goes down by one and the value is moved out. Removing the first element is O(n), because every remaining element has to move down one place to keep the block starting at the beginning. Vec does offer that operation, as v.remove(0).

There are two tempting ways to make the starter compile with a Vec:

• queue.remove(0) gives the correct BFS order, but each removal moves every element still in the queue. On a graph with V nodes and E edges, a BFS with an O(1) queue does O(V + E) work. With remove(0) the shifting alone can cost O(V²) in the worst case, for example when the start node has an edge to every other node.
• queue.pop() compiles and never panics, but it takes the newest node instead of the oldest. The container is now a stack, and the result is not breadth-first. The first test case catches this. For adj = [[1,2],[3],[3],[]] from node 0, BFS visits [0,1,2,3]. The stack version visits [0,2,3,1]: it pushes 1 and 2, pops 2 first, then pushes and pops 3, and only then pops 1.

The stack version is a depth-first style traversal, but because it marks nodes when they are pushed it does not always match the order of a recursive depth-first search (DFS). A recursive DFS of the same graph that follows each list in order visits [0,1,3,2].

What a VecDeque is

std::collections::VecDeque is a double-ended queue, implemented as a growable ring buffer. A ring buffer is a single block of memory in which the first element does not have to sit at the start of the block. The deque remembers where its first element is and how many elements it has, and the elements may run off the end of the block and continue at its beginning.

Because the front is just a stored position, removing the first element does not move anything. Adding or removing at either end is O(1). Adding can occasionally need to grow the buffer, which copies the elements, so the push methods are O(1) amortised: averaged over many pushes, the cost per push is constant.

use std::collections::VecDeque;

let mut q: VecDeque<usize> = VecDeque::new();
q.push_back(1);     // q is [1]
q.push_front(0);    // q is [0, 1]
q.push_back(2);     // q is [0, 1, 2]
assert_eq!(q.front(), Some(&0));
assert_eq!(q.back(), Some(&2));
assert_eq!(q.pop_front(), Some(0));   // q is [1, 2]
assert_eq!(q.pop_back(), Some(2));    // q is [1]

A first-in, first-out queue uses push_back and pop_front. A last-in, first-out stack uses push_back and pop_back. In the traversal above, that one choice is the difference between the BFS order and the stack order.

The usual loop is:

while let Some(node) = queue.pop_front() {
    // handle `node`
}

pop_front returns Some(node) while the queue has elements and None once it is empty, so the loop ends exactly when the queue is drained. There is no separate is_empty check and no unwrap.

A VecDeque is not one slice

Since the elements can wrap around the end of the buffer, a VecDeque cannot in general give you a single &[T]. as_slices returns two slices: the part from the first element to the end of the buffer, and the part that wrapped around to the beginning.

use std::collections::VecDeque;

let mut d: VecDeque<i32> = VecDeque::with_capacity(8);
for i in 0..6 {
    d.push_back(i);       // buffer positions 0..6 hold 0..6
}
d.pop_front();
d.pop_front();
d.pop_front();            // the first element, 3, is at position 3
d.push_back(100);
d.push_back(101);         // positions 6 and 7: the end of the buffer
d.push_back(102);         // wraps around to position 0

println!("{:?}", d.as_slices()); // ([3, 4, 5, 100, 101], [102])

The exact split depends on the buffer's capacity and on how std places elements, neither of which the documentation promises. with_capacity(8) only guarantees room for at least 8 elements. The output shown is what the current implementation prints, where the capacity here is exactly 8. Code should not rely on where the split falls.

iter() hides the split and yields 3, 4, 5, 100, 101, 102 in order. When you need one contiguous slice, for example to pass the contents to a function that takes &[T], call make_contiguous(). It rearranges the elements inside the existing buffer so they no longer wrap, which can cost O(n), and returns a single &mut [T]. A Vec can always give you a slice because its elements are always contiguous.

Iterating over the neighbours

The starter walks each neighbour list by index:

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

Iterating over the list directly says the same thing more simply:

for &next in &adj[node] {

&adj[node] borrows the list, the loop yields a &usize for each entry, and the &next pattern copies the number out. There is no index variable to get wrong.

Your solution is also checked with cargo clippy -- -D warnings, which turns every warning Clippy reports into an error. Clippy's needless_range_loop lint warns about a for i in 0..v.len() loop whose index is only used to read v[i]. With Rust 1.98.1 the starter's loop, once the queue is fixed so it compiles, triggers it (the loop variable i is only used to index adj) and fails that check. Whether the lint fires depends on the rest of the loop body: adding the required next < adj.len() test uses adj for something other than indexing, and the warning goes away. Iterating directly avoids the question.