1037 Intermediate

1037-adjacency-list — Adjacency List Graph

Functional Programming

Tutorial

The Problem

The adjacency list representation stores a graph as a map from each node to its list of neighbors. Compared to an adjacency matrix (O(V²) space), the adjacency list uses O(V + E) space, making it optimal for sparse graphs — social networks, web graphs, and road maps all have far fewer edges than the V² maximum.

This is the representation behind breadth-first search (BFS), depth-first search (DFS), Dijkstra's algorithm, and most graph algorithms in practice.

🎯 Learning Outcomes

• Represent a directed graph as HashMap<usize, Vec<usize>>

• Add nodes and edges with O(1) amortized complexity

• Implement BFS using VecDeque for the frontier queue

• Implement DFS using recursion or an explicit stack

• Understand the trade-offs between adjacency list and adjacency matrix

Code Example

#![allow(clippy::all)]
// 1037: Adjacency List — HashMap<usize, Vec<usize>>
// Classic graph representation with BFS and DFS

use std::collections::{HashMap, HashSet, VecDeque};

/// Adjacency list graph
struct Graph {
    adj: HashMap<usize, Vec<usize>>,
}

impl Graph {
    fn new() -> Self {
        Graph {
            adj: HashMap::new(),
        }
    }

    fn add_edge(&mut self, from: usize, to: usize) {
        self.adj.entry(from).or_default().push(to);
        // Ensure 'to' node exists in the map
        self.adj.entry(to).or_default();
    }

    fn neighbors(&self, node: usize) -> &[usize] {
        self.adj.get(&node).map_or(&[], |v| v.as_slice())
    }

    /// BFS traversal
    fn bfs(&self, start: usize) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        let mut order = Vec::new();

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

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

    /// DFS traversal (recursive)
    fn dfs(&self, start: usize) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut order = Vec::new();
        self.dfs_helper(start, &mut visited, &mut order);
        order
    }

    fn dfs_helper(&self, node: usize, visited: &mut HashSet<usize>, order: &mut Vec<usize>) {
        if !visited.insert(node) {
            return;
        }
        order.push(node);
        for &neighbor in self.neighbors(node) {
            self.dfs_helper(neighbor, visited, order);
        }
    }

    /// Find shortest path using BFS
    fn find_path(&self, start: usize, goal: usize) -> Option<Vec<usize>> {
        let mut visited = HashSet::new();
        let mut parent: HashMap<usize, usize> = HashMap::new();
        let mut queue = VecDeque::new();

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

        while let Some(node) = queue.pop_front() {
            if node == goal {
                // Reconstruct path
                let mut path = vec![goal];
                let mut current = goal;
                while current != start {
                    current = parent[&current];
                    path.push(current);
                }
                path.reverse();
                return Some(path);
            }
            for &neighbor in self.neighbors(node) {
                if visited.insert(neighbor) {
                    parent.insert(neighbor, node);
                    queue.push_back(neighbor);
                }
            }
        }
        None
    }
}

fn test_bfs_dfs() {
    let mut g = Graph::new();
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 3);
    g.add_edge(2, 3);
    g.add_edge(3, 4);

    let bfs_order = g.bfs(0);
    assert_eq!(bfs_order.len(), 5);
    assert_eq!(bfs_order[0], 0);
    assert!(bfs_order.contains(&4));

    let dfs_order = g.dfs(0);
    assert_eq!(dfs_order.len(), 5);
    assert_eq!(dfs_order[0], 0);
}

fn test_path_finding() {
    let mut g = Graph::new();
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 3);
    g.add_edge(2, 3);
    g.add_edge(3, 4);

    let path = g.find_path(0, 4).unwrap();
    assert_eq!(*path.first().unwrap(), 0);
    assert_eq!(*path.last().unwrap(), 4);
    assert!(path.len() <= 4); // Shortest path is 3 hops

    assert!(g.find_path(4, 0).is_none()); // No path back (directed)
}

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

    #[test]
    fn test_bfs() {
        test_bfs_dfs();
    }

    #[test]
    fn test_paths() {
        test_path_finding();
    }

    #[test]
    fn test_disconnected() {
        let mut g = Graph::new();
        g.add_edge(0, 1);
        g.add_edge(2, 3);
        let reachable = g.bfs(0);
        assert_eq!(reachable.len(), 2); // Only 0 and 1
        assert!(!reachable.contains(&2));
    }

    #[test]
    fn test_self_loop() {
        let mut g = Graph::new();
        g.add_edge(0, 0);
        g.add_edge(0, 1);
        let order = g.bfs(0);
        assert_eq!(order.len(), 2);
    }
}

(* 1037: Adjacency List — BFS and DFS *)
(* Graph represented as a map from node to list of neighbors *)

module IntMap = Map.Make(Int)

type graph = int list IntMap.t

let empty_graph : graph = IntMap.empty

let add_edge g from_n to_n =
  let neighbors = match IntMap.find_opt from_n g with
    | Some ns -> ns
    | None -> []
  in
  IntMap.add from_n (to_n :: neighbors) g

let neighbors g node =
  match IntMap.find_opt node g with
  | Some ns -> ns
  | None -> []

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

(* Approach 2: DFS (recursive) *)
let dfs g start =
  let visited = Hashtbl.create 16 in
  let order = ref [] in
  let rec visit node =
    if not (Hashtbl.mem visited node) then begin
      Hashtbl.add visited node true;
      order := node :: !order;
      List.iter visit (neighbors g node)
    end
  in
  visit start;
  List.rev !order

(* Approach 3: Path finding with BFS *)
let find_path g start goal =
  let visited = Hashtbl.create 16 in
  let parent = Hashtbl.create 16 in
  let queue = Queue.create () in
  Queue.push start queue;
  Hashtbl.add visited start true;
  let found = ref false in
  while not (Queue.is_empty queue) && not !found do
    let node = Queue.pop queue in
    if node = goal then found := true
    else
      List.iter (fun neighbor ->
        if not (Hashtbl.mem visited neighbor) then begin
          Hashtbl.add visited neighbor true;
          Hashtbl.add parent neighbor node;
          Queue.push neighbor queue
        end
      ) (neighbors g node)
  done;
  if not !found then None
  else begin
    let rec build_path node acc =
      if node = start then start :: acc
      else build_path (Hashtbl.find parent node) (node :: acc)
    in
    Some (build_path goal [])
  end

let () =
  (* Build graph: 0->1, 0->2, 1->3, 2->3, 3->4 *)
  let g = empty_graph
    |> fun g -> add_edge g 0 1
    |> fun g -> add_edge g 0 2
    |> fun g -> add_edge g 1 3
    |> fun g -> add_edge g 2 3
    |> fun g -> add_edge g 3 4
  in
  let bfs_order = bfs g 0 in
  assert (List.mem 0 bfs_order);
  assert (List.mem 4 bfs_order);
  assert (List.length bfs_order = 5);

  let dfs_order = dfs g 0 in
  assert (List.hd dfs_order = 0);
  assert (List.length dfs_order = 5);

  let path = find_path g 0 4 in
  assert (path <> None);
  let path = Option.get path in
  assert (List.hd path = 0);
  assert (List.nth path (List.length path - 1) = 4);

  Printf.printf "✓ All tests passed\n"

Key Differences

Mutability: Rust's HashMap-based graph is mutable (push in place); OCaml's Map-based graph is immutable (each update returns a new version).

Node initialization: Rust's entry().or_default() ensures the node exists even with no edges; OCaml requires explicit handling of Not_found.

BFS queue: Rust uses VecDeque for O(1) front dequeue; OCaml's Queue module provides the same, or List is used (O(n) dequeue).

Visited set: Both use a hash set for visited tracking; Rust's HashSet and OCaml's Hashtbl-based set serve the same purpose.

OCaml Approach

OCaml's adjacency list uses a map or array:

module IntMap = Map.Make(Int)

type graph = int list IntMap.t

let add_edge g from_ to_ =
  let neighbors = try IntMap.find from_ g with Not_found -> [] in
  IntMap.add from_ (to_ :: neighbors) g

OCaml's immutable map means each add_edge creates a new graph version — appropriate for purely functional graph algorithms but less efficient for incremental construction.

Full Source

#![allow(clippy::all)]
// 1037: Adjacency List — HashMap<usize, Vec<usize>>
// Classic graph representation with BFS and DFS

use std::collections::{HashMap, HashSet, VecDeque};

/// Adjacency list graph
struct Graph {
    adj: HashMap<usize, Vec<usize>>,
}

impl Graph {
    fn new() -> Self {
        Graph {
            adj: HashMap::new(),
        }
    }

    fn add_edge(&mut self, from: usize, to: usize) {
        self.adj.entry(from).or_default().push(to);
        // Ensure 'to' node exists in the map
        self.adj.entry(to).or_default();
    }

    fn neighbors(&self, node: usize) -> &[usize] {
        self.adj.get(&node).map_or(&[], |v| v.as_slice())
    }

    /// BFS traversal
    fn bfs(&self, start: usize) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        let mut order = Vec::new();

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

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

    /// DFS traversal (recursive)
    fn dfs(&self, start: usize) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut order = Vec::new();
        self.dfs_helper(start, &mut visited, &mut order);
        order
    }

    fn dfs_helper(&self, node: usize, visited: &mut HashSet<usize>, order: &mut Vec<usize>) {
        if !visited.insert(node) {
            return;
        }
        order.push(node);
        for &neighbor in self.neighbors(node) {
            self.dfs_helper(neighbor, visited, order);
        }
    }

    /// Find shortest path using BFS
    fn find_path(&self, start: usize, goal: usize) -> Option<Vec<usize>> {
        let mut visited = HashSet::new();
        let mut parent: HashMap<usize, usize> = HashMap::new();
        let mut queue = VecDeque::new();

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

        while let Some(node) = queue.pop_front() {
            if node == goal {
                // Reconstruct path
                let mut path = vec![goal];
                let mut current = goal;
                while current != start {
                    current = parent[&current];
                    path.push(current);
                }
                path.reverse();
                return Some(path);
            }
            for &neighbor in self.neighbors(node) {
                if visited.insert(neighbor) {
                    parent.insert(neighbor, node);
                    queue.push_back(neighbor);
                }
            }
        }
        None
    }
}

fn test_bfs_dfs() {
    let mut g = Graph::new();
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 3);
    g.add_edge(2, 3);
    g.add_edge(3, 4);

    let bfs_order = g.bfs(0);
    assert_eq!(bfs_order.len(), 5);
    assert_eq!(bfs_order[0], 0);
    assert!(bfs_order.contains(&4));

    let dfs_order = g.dfs(0);
    assert_eq!(dfs_order.len(), 5);
    assert_eq!(dfs_order[0], 0);
}

fn test_path_finding() {
    let mut g = Graph::new();
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 3);
    g.add_edge(2, 3);
    g.add_edge(3, 4);

    let path = g.find_path(0, 4).unwrap();
    assert_eq!(*path.first().unwrap(), 0);
    assert_eq!(*path.last().unwrap(), 4);
    assert!(path.len() <= 4); // Shortest path is 3 hops

    assert!(g.find_path(4, 0).is_none()); // No path back (directed)
}

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

    #[test]
    fn test_bfs() {
        test_bfs_dfs();
    }

    #[test]
    fn test_paths() {
        test_path_finding();
    }

    #[test]
    fn test_disconnected() {
        let mut g = Graph::new();
        g.add_edge(0, 1);
        g.add_edge(2, 3);
        let reachable = g.bfs(0);
        assert_eq!(reachable.len(), 2); // Only 0 and 1
        assert!(!reachable.contains(&2));
    }

    #[test]
    fn test_self_loop() {
        let mut g = Graph::new();
        g.add_edge(0, 0);
        g.add_edge(0, 1);
        let order = g.bfs(0);
        assert_eq!(order.len(), 2);
    }
}

(* 1037: Adjacency List — BFS and DFS *)
(* Graph represented as a map from node to list of neighbors *)

module IntMap = Map.Make(Int)

type graph = int list IntMap.t

let empty_graph : graph = IntMap.empty

let add_edge g from_n to_n =
  let neighbors = match IntMap.find_opt from_n g with
    | Some ns -> ns
    | None -> []
  in
  IntMap.add from_n (to_n :: neighbors) g

let neighbors g node =
  match IntMap.find_opt node g with
  | Some ns -> ns
  | None -> []

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

(* Approach 2: DFS (recursive) *)
let dfs g start =
  let visited = Hashtbl.create 16 in
  let order = ref [] in
  let rec visit node =
    if not (Hashtbl.mem visited node) then begin
      Hashtbl.add visited node true;
      order := node :: !order;
      List.iter visit (neighbors g node)
    end
  in
  visit start;
  List.rev !order

(* Approach 3: Path finding with BFS *)
let find_path g start goal =
  let visited = Hashtbl.create 16 in
  let parent = Hashtbl.create 16 in
  let queue = Queue.create () in
  Queue.push start queue;
  Hashtbl.add visited start true;
  let found = ref false in
  while not (Queue.is_empty queue) && not !found do
    let node = Queue.pop queue in
    if node = goal then found := true
    else
      List.iter (fun neighbor ->
        if not (Hashtbl.mem visited neighbor) then begin
          Hashtbl.add visited neighbor true;
          Hashtbl.add parent neighbor node;
          Queue.push neighbor queue
        end
      ) (neighbors g node)
  done;
  if not !found then None
  else begin
    let rec build_path node acc =
      if node = start then start :: acc
      else build_path (Hashtbl.find parent node) (node :: acc)
    in
    Some (build_path goal [])
  end

let () =
  (* Build graph: 0->1, 0->2, 1->3, 2->3, 3->4 *)
  let g = empty_graph
    |> fun g -> add_edge g 0 1
    |> fun g -> add_edge g 0 2
    |> fun g -> add_edge g 1 3
    |> fun g -> add_edge g 2 3
    |> fun g -> add_edge g 3 4
  in
  let bfs_order = bfs g 0 in
  assert (List.mem 0 bfs_order);
  assert (List.mem 4 bfs_order);
  assert (List.length bfs_order = 5);

  let dfs_order = dfs g 0 in
  assert (List.hd dfs_order = 0);
  assert (List.length dfs_order = 5);

  let path = find_path g 0 4 in
  assert (path <> None);
  let path = Option.get path in
  assert (List.hd path = 0);
  assert (List.nth path (List.length path - 1) = 4);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_bfs() {
        test_bfs_dfs();
    }

    #[test]
    fn test_paths() {
        test_path_finding();
    }

    #[test]
    fn test_disconnected() {
        let mut g = Graph::new();
        g.add_edge(0, 1);
        g.add_edge(2, 3);
        let reachable = g.bfs(0);
        assert_eq!(reachable.len(), 2); // Only 0 and 1
        assert!(!reachable.contains(&2));
    }

    #[test]
    fn test_self_loop() {
        let mut g = Graph::new();
        g.add_edge(0, 0);
        g.add_edge(0, 1);
        let order = g.bfs(0);
        assert_eq!(order.len(), 2);
    }
}

Deep Comparison

Adjacency List Graph — Comparison

Core Insight

Adjacency lists are the most common graph representation for sparse graphs. Both languages map a node ID to its list of neighbors. The main API difference is Rust's HashSet::insert() returning a boolean (replaces the check-then-mark pattern).

OCaml Approach

• IntMap.t mapping node to int list of neighbors

• Hashtbl for visited set (mutable)

• Queue module for BFS

• Recursive function for DFS

• Path reconstruction via parent hashtable

Rust Approach

• HashMap<usize, Vec<usize>> for adjacency list

• HashSet::insert() returns false if already present — combines check + insert

• VecDeque for BFS queue

• Recursive DFS with &mut HashSet for visited

• map_or(&[], ...) for safe neighbor access

Comparison Table

Feature	OCaml	Rust
Adjacency list	`int list IntMap.t`	`HashMap<usize, Vec<usize>>`
Visited set	`Hashtbl` + `mem`	`HashSet` + `insert` (returns bool)
BFS queue	`Queue` module	`VecDeque`
DFS	Recursive + Hashtbl	Recursive + `&mut HashSet`
Edge lookup	O(log n) Map	O(1) HashMap
Neighbor access	`find_opt` + default	`map_or(&[], ...)`

Exercises

Add a has_cycle method that detects cycles using DFS with a color-marking scheme (white/gray/black).

Implement an undirected graph variant where add_edge(a, b) automatically adds both a -> b and b -> a.

Write shortest_path(start: usize, end_: usize) -> Option<Vec<usize>> using BFS with parent tracking to reconstruct the path.

Open Source Repos

functional-rust

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

Rust