Graphs

Shortest Path (Unweighted, via BFS)

BFS explores a graph layer by layer, so the first time it reaches a vertex is along a shortest path. Track dist[v] and parent[v] while exploring, then walk parents back from the target to reconstruct the route.

Algorithm

On the canonical graph from graph-adjacency-list, the shortest path from 1 to 6 is [1, 2, 4, 5, 6] with distance 4. The path is rebuilt from parent: 6 -> 5 -> 4 -> 2 -> 1, reversed.

layers equal distance BFS order equals distance in an unweighted graph.

Basic Implementation

basic.rs
Replay: real traced execution (multi-file project)
use std::collections::HashMap;
use std::collections::VecDeque;
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 src = 1;
	let dst = 6;
	let mut dist: HashMap<i32, i32> = HashMap::new();
	let mut parent: HashMap<i32, i32> = HashMap::new();
	dist.insert(src, 0);
	parent.insert(src, 0);
	let mut queue: VecDeque<i32> = VecDeque::new();
	queue.push_back(src);
	while let Some(v) = queue.pop_front() {
		for &nb in &adj[&v] {
			if !dist.contains_key(&nb) {
				let d = dist[&v] + 1;
				dist.insert(nb, d);
				parent.insert(nb, v);
				queue.push_back(nb);
			}
		}
	}
	let mut path: Vec<i32> = Vec::new();
	let mut node = dst;
	while node != 0 {
		path.push(node);
		node = parent[&node];
	}
	path.reverse();
	println!("{:?}", path);
	println!("{}", dist[&dst]);
}

  1. dist ← {1: 0}

    14let mut parent: HashMap<i32, i32> = HashMap::new();15dist.insert(src, 0);16parent.insert(src, 0);
    values this step{1: 0}dist

  2. parent ← {1: null}

    15dist.insert(src, 0);16parent.insert(src, 0);17let mut queue: VecDeque<i32> = VecDeque::new();
    values this step{1: null}parent

  3. dist ← {1: 0, 2: 1, 3: 1}, parent ← {1: null, 2: 1, 3: 1}, queue ← [2, 3]

    18queue.push_back(src);19while let Some(v) = queue.pop_front() {20	for &nb in &adj[&v] {
    values this step{1: 0, 2: 1, 3: 1}dist{1: null, 2: 1, 3: 1}parent[2, 3]queue1dequeue

  4. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    18queue.push_back(src);19while let Some(v) = queue.pop_front() {20	for &nb in &adj[&v] {
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[3, 4]queue2dequeue

  5. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    18queue.push_back(src);19while let Some(v) = queue.pop_front() {20	for &nb in &adj[&v] {
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[4]queue3dequeue

  6. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4}

    18queue.push_back(src);19while let Some(v) = queue.pop_front() {20	for &nb in &adj[&v] {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4}parent[5]queue4dequeue

  7. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    18queue.push_back(src);19while let Some(v) = queue.pop_front() {20	for &nb in &adj[&v] {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[6]queue5dequeue

  8. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    18queue.push_back(src);19while let Some(v) = queue.pop_front() {20	for &nb in &adj[&v] {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[]queue6dequeue

  9. path ← [1, 2, 4, 5, 6]

    29let mut path: Vec<i32> = Vec::new();30let mut node = dst;31while node != 0 {
    values this step[1, 2, 4, 5, 6]path{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent

  10. stdout ← [1, 2, 4, 5, 6]

    35path.reverse();36println!("{:?}", path);37println!("{}", dist[&dst]);
    values this step[1, 2, 4, 5, 6]stdout[1, 2, 4, 5, 6]path

  11. stdout ← 4

    36	println!("{:?}", path);37	println!("{}", dist[&dst]);38}
    values this step4stdout4dist[6]

  12. BFS path ← 1 -> 2 (1 edge, cost 10), cheaper weighted path ← 1 -> 3 -> 2 (2 edges, cost 2)

    36	println!("{:?}", path);37	println!("{}", dist[&dst]);38}
    values this step1 -> 2 (1 edge, cost 10)BFS path1 -> 3 -> 2 (2 edges, cost 2)cheaper weighted pathuse Dijkstra with a priority queueweighted algorithm1->2 weight 10, 1->3 weight 1, 3->2 weight 1edge weights

Complexity

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

Implementation notes

  • Rust: a dist HashMap doubles as the visited check, parent records predecessors (0 marks the source), and a VecDeque gives FIFO order.
  • The replay shows dist, parent, and the queue filling in, then the reconstructed path. It also contrasts that unweighted result with a weighted graph where Dijkstra with a priority queue is required.