Breadth-First Search

From a start vertex, explore the graph layer by layer. Use a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours.

Algorithm

Canonical adjacency list:

1 -> [2, 3]
2 -> [1, 4]
3 -> [1, 4]
4 -> [2, 3, 5]
5 -> [4, 6]
6 -> [5]

Starting at vertex 1, the BFS visit order is [1, 2, 3, 4, 5, 6].

Basic Implementation

basic.rs

use std::collections::HashMap;

fn main() {
	let mut adj: HashMap<i32, Vec<i32>> = HashMap::new();
	adj.insert(1, vec![2, 3]);
	adj.insert(2, vec![1, 4]);
	adj.insert(3, vec![1, 4]);
	adj.insert(4, vec![2, 3, 5]);
	adj.insert(5, vec![4, 6]);
	adj.insert(6, vec![5]);
	let start = 1;
	let mut visited: HashMap<i32, bool> = HashMap::new();
	visited.insert(start, true);
	let mut queue: Vec<i32> = vec![start];
	let mut order: Vec<i32> = Vec::new();
	while !queue.is_empty() {
		let v = queue.remove(0);
		order.push(v);
		let neighbours = adj[&v].clone();
		for nb in neighbours {
			if !visited.contains_key(&nb) {
				visited.insert(nb, true);
				queue.push(nb);
			}
		}
	}
	println!("{:?}", order);
}

Complexity

Time: O(V + E)
Space: O(V)

Implementation notes

Rust: HashMap<i32, Vec<i32>> is the idiomatic adjacency list and keeps the vertex iteration shape visible; the lesson does not lean on std::collections::VecDeque (which would still teach the same shape) so the queue stays a plain Vec<i32>.
A HashMap<i32, bool> is the explicit "visited" set; the queue is a plain Vec<i32> with queue.remove(0) for dequeue and queue.push(...) for enqueue. remove(0) is O(n) but the canonical input has six vertices, so it stays honest.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue A plain `Vec<i32>` with `queue.remove(0)` for dequeue and `queue.push` for enqueue implements FIFO without hiding the iteration shape.

visited-before-enqueue Mark a vertex visited before pushing it onto the queue. Keeps the queue size bounded by V.