253 Intermediate

Graph BFS

Graphs

Tutorial Video

Text description (accessibility)

This video demonstrates the "Graph BFS" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Graphs. Perform a breadth-first search (BFS) on a graph represented as an adjacency list, returning all reachable nodes in level-order (closest nodes first). Key difference from OCaml: 1. **Graph representation:** OCaml uses `(key, value) list` with `List.assoc` (O(n) lookup); Rust uses `HashMap` (O(1) average lookup).

Tutorial

The Problem

Perform a breadth-first search (BFS) on a graph represented as an adjacency list, returning all reachable nodes in level-order (closest nodes first).

🎯 Learning Outcomes

• How to model graphs in Rust using HashMap<&str, Vec<&str>> vs OCaml's association lists

• Why VecDeque is the natural replacement for OCaml's mutable Queue

• How HashSet::insert returns a boolean, enabling a clean visited-check-and-mark in one step

• The difference between mutable imperative BFS (OCaml + Rust both support it) and purely functional BFS

🦀 The Rust Way

Rust mirrors the imperative OCaml style closely: HashSet replaces Hashtbl, VecDeque replaces Queue, and HashMap replaces the association list. The key idiom is if visited.insert(neighbor) — HashSet::insert returns false if the element was already present, combining the membership test and insertion into one expression.

Code Example

pub fn bfs<'a>(graph: &'a HashMap<&str, Vec<&str>>, start: &'a str) -> Vec<&'a str> {
    let mut visited: HashSet<&str> = HashSet::new();
    let mut queue: VecDeque<&str> = VecDeque::new();
    let mut result: Vec<&str> = Vec::new();

    queue.push_back(start);
    visited.insert(start);

    while let Some(node) = queue.pop_front() {
        result.push(node);
        if let Some(neighbors) = graph.get(node) {
            for &neighbor in neighbors {
                if visited.insert(neighbor) {
                    queue.push_back(neighbor);
                }
            }
        }
    }

    result
}

let bfs graph start =
  let visited = Hashtbl.create 16 in
  let queue = Queue.create () in
  Queue.push start queue;
  Hashtbl.add visited start true;
  let result = ref [] in
  while not (Queue.is_empty queue) do
    let node = Queue.pop queue in
    result := node :: !result;
    List.iter (fun neighbor ->
      if not (Hashtbl.mem visited neighbor) then begin
        Hashtbl.add visited neighbor true;
        Queue.push neighbor queue
      end
    ) (List.assoc node graph)
  done;
  List.rev !result

Key Differences

Graph representation: OCaml uses (key, value) list with List.assoc (O(n) lookup); Rust uses HashMap (O(1) average lookup).

Queue: OCaml's Queue is doubly-ended by default; Rust's VecDeque is explicit about push/pop ends (push_back / pop_front).

Visited set: OCaml uses Hashtbl.mem + Hashtbl.add (two operations); Rust's HashSet::insert returns a bool, combining both into one.

Result accumulation: OCaml uses a ref list prepended in reverse then List.rev; Rust uses Vec::push directly in order.

OCaml Approach

OCaml uses a mutable Hashtbl for visited tracking and a mutable Queue for the frontier, iterating with a while loop. The graph is an association list (string * string list) list, looked up with List.assoc. The result accumulates in a ref list that is reversed at the end.

Full Source

#![allow(clippy::all)]
use std::collections::{HashMap, HashSet, VecDeque};

/// Idiomatic Rust BFS: uses HashMap for adjacency list, VecDeque as queue,
/// HashSet for visited tracking. Returns nodes in BFS order.
pub fn bfs<'a>(graph: &'a HashMap<&str, Vec<&str>>, start: &'a str) -> Vec<&'a str> {
    let mut visited: HashSet<&str> = HashSet::new();
    let mut queue: VecDeque<&str> = VecDeque::new();
    let mut result: Vec<&str> = Vec::new();

    queue.push_back(start);
    visited.insert(start);

    while let Some(node) = queue.pop_front() {
        result.push(node);
        if let Some(neighbors) = graph.get(node) {
            for &neighbor in neighbors {
                if visited.insert(neighbor) {
                    // insert returns true if the value was not already present
                    queue.push_back(neighbor);
                }
            }
        }
    }

    result
}

/// Functional-style BFS using slice-based adjacency list (closer to OCaml).
/// The graph is a slice of (node, neighbors) pairs — mirrors `List.assoc`.
pub fn bfs_assoc<'a>(graph: &[(&'a str, Vec<&'a str>)], start: &'a str) -> Vec<&'a str> {
    let mut visited: HashSet<&str> = HashSet::new();
    let mut queue: VecDeque<&str> = VecDeque::new();
    let mut result: Vec<&str> = Vec::new();

    queue.push_back(start);
    visited.insert(start);

    while let Some(node) = queue.pop_front() {
        result.push(node);
        // Mirror OCaml's List.assoc: find neighbors for this node
        if let Some((_, neighbors)) = graph.iter().find(|(n, _)| *n == node) {
            for &neighbor in neighbors {
                if visited.insert(neighbor) {
                    queue.push_back(neighbor);
                }
            }
        }
    }

    result
}

#[cfg(test)]
mod tests {
    use super::*;

    fn make_graph() -> HashMap<&'static str, Vec<&'static str>> {
        let mut g = HashMap::new();
        g.insert("a", vec!["b", "c"]);
        g.insert("b", vec!["d"]);
        g.insert("c", vec!["d"]);
        g.insert("d", vec![]);
        g
    }

    #[test]
    fn test_bfs_visits_all_nodes() {
        let graph = make_graph();
        let order = bfs(&graph, "a");
        // All four nodes must appear exactly once
        assert_eq!(order.len(), 4);
        let mut sorted = order.clone();
        sorted.sort_unstable();
        assert_eq!(sorted, vec!["a", "b", "c", "d"]);
    }

    #[test]
    fn test_bfs_start_node_is_first() {
        let graph = make_graph();
        let order = bfs(&graph, "a");
        assert_eq!(order[0], "a");
    }

    #[test]
    fn test_bfs_level_order() {
        let graph = make_graph();
        let order = bfs(&graph, "a");
        // "a" must come before "b" and "c"; "b" and "c" before "d"
        let pos: HashMap<&str, usize> = order.iter().enumerate().map(|(i, &n)| (n, i)).collect();
        assert!(pos["a"] < pos["b"]);
        assert!(pos["a"] < pos["c"]);
        assert!(pos["b"] < pos["d"]);
        assert!(pos["c"] < pos["d"]);
    }

    #[test]
    fn test_bfs_single_node() {
        let mut graph = HashMap::new();
        graph.insert("x", vec![]);
        let order = bfs(&graph, "x");
        assert_eq!(order, vec!["x"]);
    }

    #[test]
    fn test_bfs_linear_chain() {
        let mut graph = HashMap::new();
        graph.insert("1", vec!["2"]);
        graph.insert("2", vec!["3"]);
        graph.insert("3", vec![]);
        let order = bfs(&graph, "1");
        assert_eq!(order, vec!["1", "2", "3"]);
    }

    #[test]
    fn test_bfs_assoc_matches_ocaml() {
        let graph = vec![
            ("a", vec!["b", "c"]),
            ("b", vec!["d"]),
            ("c", vec!["d"]),
            ("d", vec![]),
        ];
        let order = bfs_assoc(&graph, "a");
        // Same reachability guarantee as OCaml version
        assert_eq!(order[0], "a");
        assert_eq!(order.len(), 4);
        let mut sorted = order.clone();
        sorted.sort_unstable();
        assert_eq!(sorted, vec!["a", "b", "c", "d"]);
    }

    #[test]
    fn test_bfs_no_duplicate_visits() {
        // Diamond graph: a->b, a->c, b->d, c->d — d reachable via two paths
        let mut graph = HashMap::new();
        graph.insert("a", vec!["b", "c"]);
        graph.insert("b", vec!["d"]);
        graph.insert("c", vec!["d"]);
        graph.insert("d", vec![]);
        let order = bfs(&graph, "a");
        // d must appear exactly once despite two paths leading to it
        let d_count = order.iter().filter(|&&n| n == "d").count();
        assert_eq!(d_count, 1);
    }
}

(* Idiomatic OCaml BFS: Hashtbl for visited, Queue for frontier *)
let bfs graph start =
  let visited = Hashtbl.create 16 in
  let queue = Queue.create () in
  Queue.push start queue;
  Hashtbl.add visited start true;
  let result = ref [] in
  while not (Queue.is_empty queue) do
    let node = Queue.pop queue in
    result := node :: !result;
    List.iter (fun neighbor ->
      if not (Hashtbl.mem visited neighbor) then begin
        Hashtbl.add visited neighbor true;
        Queue.push neighbor queue
      end
    ) (List.assoc node graph)
  done;
  List.rev !result

(* Purely functional BFS using list-based queue — shows explicit recursion *)
let bfs_pure graph start =
  let rec loop visited queue result =
    match queue with
    | [] -> List.rev result
    | node :: rest ->
      let neighbors = List.assoc node graph in
      let new_nodes = List.filter (fun n -> not (List.mem n visited)) neighbors in
      loop (visited @ new_nodes) (rest @ new_nodes) (node :: result)
  in
  loop [start] [start] []

let () =
  let graph = [("a", ["b";"c"]); ("b", ["d"]); ("c", ["d"]); ("d", [])] in
  let order = bfs graph "a" in
  assert (List.hd order = "a");
  assert (List.length order = 4);
  assert (List.mem "d" order);
  let order2 = bfs_pure graph "a" in
  assert (List.hd order2 = "a");
  assert (List.length order2 = 4);
  print_endline "ok"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    fn make_graph() -> HashMap<&'static str, Vec<&'static str>> {
        let mut g = HashMap::new();
        g.insert("a", vec!["b", "c"]);
        g.insert("b", vec!["d"]);
        g.insert("c", vec!["d"]);
        g.insert("d", vec![]);
        g
    }

    #[test]
    fn test_bfs_visits_all_nodes() {
        let graph = make_graph();
        let order = bfs(&graph, "a");
        // All four nodes must appear exactly once
        assert_eq!(order.len(), 4);
        let mut sorted = order.clone();
        sorted.sort_unstable();
        assert_eq!(sorted, vec!["a", "b", "c", "d"]);
    }

    #[test]
    fn test_bfs_start_node_is_first() {
        let graph = make_graph();
        let order = bfs(&graph, "a");
        assert_eq!(order[0], "a");
    }

    #[test]
    fn test_bfs_level_order() {
        let graph = make_graph();
        let order = bfs(&graph, "a");
        // "a" must come before "b" and "c"; "b" and "c" before "d"
        let pos: HashMap<&str, usize> = order.iter().enumerate().map(|(i, &n)| (n, i)).collect();
        assert!(pos["a"] < pos["b"]);
        assert!(pos["a"] < pos["c"]);
        assert!(pos["b"] < pos["d"]);
        assert!(pos["c"] < pos["d"]);
    }

    #[test]
    fn test_bfs_single_node() {
        let mut graph = HashMap::new();
        graph.insert("x", vec![]);
        let order = bfs(&graph, "x");
        assert_eq!(order, vec!["x"]);
    }

    #[test]
    fn test_bfs_linear_chain() {
        let mut graph = HashMap::new();
        graph.insert("1", vec!["2"]);
        graph.insert("2", vec!["3"]);
        graph.insert("3", vec![]);
        let order = bfs(&graph, "1");
        assert_eq!(order, vec!["1", "2", "3"]);
    }

    #[test]
    fn test_bfs_assoc_matches_ocaml() {
        let graph = vec![
            ("a", vec!["b", "c"]),
            ("b", vec!["d"]),
            ("c", vec!["d"]),
            ("d", vec![]),
        ];
        let order = bfs_assoc(&graph, "a");
        // Same reachability guarantee as OCaml version
        assert_eq!(order[0], "a");
        assert_eq!(order.len(), 4);
        let mut sorted = order.clone();
        sorted.sort_unstable();
        assert_eq!(sorted, vec!["a", "b", "c", "d"]);
    }

    #[test]
    fn test_bfs_no_duplicate_visits() {
        // Diamond graph: a->b, a->c, b->d, c->d — d reachable via two paths
        let mut graph = HashMap::new();
        graph.insert("a", vec!["b", "c"]);
        graph.insert("b", vec!["d"]);
        graph.insert("c", vec!["d"]);
        graph.insert("d", vec![]);
        let order = bfs(&graph, "a");
        // d must appear exactly once despite two paths leading to it
        let d_count = order.iter().filter(|&&n| n == "d").count();
        assert_eq!(d_count, 1);
    }
}

Deep Comparison

OCaml vs Rust: Graph BFS

Side-by-Side Code

OCaml

let bfs graph start =
  let visited = Hashtbl.create 16 in
  let queue = Queue.create () in
  Queue.push start queue;
  Hashtbl.add visited start true;
  let result = ref [] in
  while not (Queue.is_empty queue) do
    let node = Queue.pop queue in
    result := node :: !result;
    List.iter (fun neighbor ->
      if not (Hashtbl.mem visited neighbor) then begin
        Hashtbl.add visited neighbor true;
        Queue.push neighbor queue
      end
    ) (List.assoc node graph)
  done;
  List.rev !result

Rust (idiomatic)

pub fn bfs<'a>(graph: &'a HashMap<&str, Vec<&str>>, start: &'a str) -> Vec<&'a str> {
    let mut visited: HashSet<&str> = HashSet::new();
    let mut queue: VecDeque<&str> = VecDeque::new();
    let mut result: Vec<&str> = Vec::new();

    queue.push_back(start);
    visited.insert(start);

    while let Some(node) = queue.pop_front() {
        result.push(node);
        if let Some(neighbors) = graph.get(node) {
            for &neighbor in neighbors {
                if visited.insert(neighbor) {
                    queue.push_back(neighbor);
                }
            }
        }
    }

    result
}

Rust (assoc-list style, mirrors OCaml)

pub fn bfs_assoc<'a>(graph: &[(&'a str, Vec<&'a str>)], start: &'a str) -> Vec<&'a str> {
    let mut visited: HashSet<&str> = HashSet::new();
    let mut queue: VecDeque<&str> = VecDeque::new();
    let mut result: Vec<&str> = Vec::new();

    queue.push_back(start);
    visited.insert(start);

    while let Some(node) = queue.pop_front() {
        result.push(node);
        if let Some((_, neighbors)) = graph.iter().find(|(n, _)| *n == node) {
            for &neighbor in neighbors {
                if visited.insert(neighbor) {
                    queue.push_back(neighbor);
                }
            }
        }
    }

    result
}

Type Signatures

Concept	OCaml	Rust
Graph type	`(string * string list) list`	`&HashMap<&str, Vec<&str>>`
Queue	`'a Queue.t` (mutable)	`VecDeque<&str>`
Visited set	`(string, bool) Hashtbl.t`	`HashSet<&str>`
Result	`string list` (via `ref` + `List.rev`)	`Vec<&str>` (pushed in order)
Neighbor lookup	`List.assoc node graph` — O(n)	`graph.get(node)` — O(1) average

Key Insights

**HashSet::insert returns bool:** OCaml needs two calls (Hashtbl.mem to check, Hashtbl.add to mark). Rust's HashSet::insert returns false if already present, enabling if visited.insert(neighbor) as a single atomic check-and-mark expression. This eliminates a TOCTOU-style bug in concurrent code and reads more clearly.

**VecDeque makes queue semantics explicit:** OCaml's Queue.push/Queue.pop always operate on the back/front respectively. Rust's VecDeque names the ends explicitly (push_back, pop_front), making the BFS invariant self-documenting in the code.

**while let Some(...) vs imperative while:** OCaml uses while not (Queue.is_empty queue) do ... Queue.pop queue — two operations. Rust's while let Some(node) = queue.pop_front() combines the emptiness check and destructuring pop into one ergonomic expression.

Association list vs HashMap: OCaml's List.assoc is idiomatic for small graphs but O(n) per lookup. Rust naturally uses HashMap for O(1) average. The bfs_assoc variant preserves the OCaml structure but at the cost of linear scans — a useful reminder that idioms have performance implications.

Result accumulation: OCaml prepends to a ref list (O(1) per step) then calls List.rev (O(n)) at the end. Rust pushes to a Vec directly in order, also O(1) amortized per step — both are linear overall, but Rust's version avoids the reversal step.

When to Use Each Style

**Use idiomatic Rust (HashMap)** when: building production graph algorithms where O(1) lookup matters, working with large graphs, or when performance is a concern.

Use assoc-list style when: porting OCaml code directly for comparison, working with very small fixed graphs, or teaching the parallel between OCaml's List.assoc and Rust's iterator find.

Exercises

Extend BFS to return the shortest-hop path between two nodes (not just distance), by recording predecessors in a HashMap during traversal.

Implement multi-source BFS: start from a set of source nodes simultaneously and find, for each node in the graph, the nearest source.

Use BFS to solve a word-ladder puzzle: build a graph where words are nodes and edges connect words differing by one letter, then find the shortest transformation sequence.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust