377 Intermediate

377: Graph — Adjacency List

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "377: Graph — Adjacency List" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Graphs model relationships between entities: social networks, road maps, dependency systems, web links. Key difference from OCaml: 1. **Storage type**: Rust uses `HashMap<usize, Vec<usize>>` for dynamic vertex sets; OCaml uses `array` of lists when vertices are dense integers, or `Hashtbl` for sparse maps.

Tutorial

The Problem

Graphs model relationships between entities: social networks, road maps, dependency systems, web links. The adjacency list representation stores for each vertex the list of its neighbors, using O(V + E) space — optimal for sparse graphs where E << V². For a social network with 1 billion users each having ~200 friends, adjacency lists use 200 billion entries versus a matrix requiring 10^18 cells.

Graph traversal algorithms (BFS, DFS) built on adjacency lists power shortest-path routing (GPS navigation), network analysis (PageRank), build system dependency resolution, and social graph recommendations.

🎯 Learning Outcomes

• Understand when adjacency lists outperform adjacency matrices (sparse graphs)

• Learn BFS and DFS traversal implementations over adjacency list graphs

• See how HashMap<usize, Vec<usize>> provides the core list structure in Rust

• Understand directed vs. undirected graph construction via conditional edge insertion

• Learn how VecDeque enables efficient BFS queue operations

Code Example

#![allow(clippy::all)]
//! Graph - Adjacency List Representation
//!
//! Space-efficient graph representation with O(V+E) storage.

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

/// Graph with adjacency list representation
pub struct Graph {
    adj: HashMap<usize, Vec<usize>>,
    directed: bool,
}

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

    pub fn add_vertex(&mut self, v: usize) {
        self.adj.entry(v).or_default();
    }

    pub fn add_edge(&mut self, u: usize, v: usize) {
        self.adj.entry(u).or_default().push(v);
        if !self.directed {
            self.adj.entry(v).or_default().push(u);
        }
        self.adj.entry(v).or_default();
    }

    pub fn neighbors(&self, u: usize) -> &[usize] {
        self.adj.get(&u).map_or(&[], Vec::as_slice)
    }

    pub fn vertices(&self) -> impl Iterator<Item = &usize> {
        self.adj.keys()
    }

    pub fn vertex_count(&self) -> usize {
        self.adj.len()
    }

    pub fn bfs(&self, start: usize) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        let mut order = Vec::new();
        queue.push_back(start);
        visited.insert(start);
        while let Some(node) = queue.pop_front() {
            order.push(node);
            let mut neighbors: Vec<_> = self.neighbors(node).to_vec();
            neighbors.sort();
            for nb in neighbors {
                if visited.insert(nb) {
                    queue.push_back(nb);
                }
            }
        }
        order
    }

    pub fn dfs(&self, start: usize) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut stack = vec![start];
        let mut order = Vec::new();
        while let Some(node) = stack.pop() {
            if visited.insert(node) {
                order.push(node);
                let mut neighbors: Vec<_> = self.neighbors(node).to_vec();
                neighbors.sort_by(|a, b| b.cmp(a));
                for nb in neighbors {
                    if !visited.contains(&nb) {
                        stack.push(nb);
                    }
                }
            }
        }
        order
    }

    pub fn has_path(&self, from: usize, to: usize) -> bool {
        self.bfs(from).contains(&to)
    }
}

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

    #[test]
    fn test_add_edge() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        assert!(g.neighbors(0).contains(&1));
        assert!(g.neighbors(0).contains(&2));
        assert!(g.neighbors(1).contains(&0));
    }

    #[test]
    fn test_directed() {
        let mut g = Graph::new(true);
        g.add_edge(0, 1);
        assert!(g.neighbors(0).contains(&1));
        assert!(!g.neighbors(1).contains(&0));
    }

    #[test]
    fn test_bfs() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        g.add_edge(1, 3);
        g.add_edge(2, 3);
        let order = g.bfs(0);
        assert_eq!(order[0], 0);
        assert!(order.contains(&1));
        assert!(order.contains(&2));
        assert!(order.contains(&3));
    }

    #[test]
    fn test_dfs() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        g.add_edge(1, 3);
        let order = g.dfs(0);
        assert_eq!(order[0], 0);
        assert_eq!(order.len(), 4);
    }

    #[test]
    fn test_has_path() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(2, 3);
        assert!(g.has_path(0, 1));
        assert!(!g.has_path(0, 2));
    }
}

(* OCaml: graph as adjacency list *)

module G = Map.Make(Int)

let add_edge g u v =
  let lu = try G.find u g with Not_found -> [] in
  let lv = try G.find v g with Not_found -> [] in
  g |> G.add u (v::lu) |> G.add v (u::lv)

let bfs g start =
  let visited = Hashtbl.create 8 in
  let queue = Queue.create () in
  Queue.add start queue;
  Hashtbl.add visited start true;
  let order = ref [] in
  while not (Queue.is_empty queue) do
    let node = Queue.pop queue in
    order := node :: !order;
    List.iter (fun nb ->
      if not (Hashtbl.mem visited nb) then begin
        Hashtbl.add visited nb true;
        Queue.add nb queue
      end
    ) (try G.find node g with Not_found -> [])
  done;
  List.rev !order

let () =
  let g = List.fold_left (fun g (u,v) -> add_edge g u v) G.empty
    [(0,1);(0,2);(1,3);(2,3);(3,4)] in
  Printf.printf "BFS from 0: [%s]\n"
    (String.concat ";" (List.map string_of_int (bfs g 0)))

Key Differences

Storage type: Rust uses HashMap<usize, Vec<usize>> for dynamic vertex sets; OCaml uses array of lists when vertices are dense integers, or Hashtbl for sparse maps.

Traversal style: Rust's BFS uses iterative VecDeque with &mut HashSet; OCaml's BFS uses Queue.t with a mutable visited array or functional Set.

Edge insertion: Rust uses entry().or_default() idiom; OCaml uses pattern matching on Hashtbl.find_opt or list prepending.

Iterator protocol: Rust's vertices() returns impl Iterator; OCaml produces lists or uses Hashtbl.iter with a callback.

OCaml Approach

OCaml represents adjacency lists as int list array (array of lists) or (int, int list) Hashtbl.t. Graph traversal uses recursive functions naturally — OCaml's stack and tail-call optimization handle DFS elegantly. BFS uses Queue.t from the standard library. The functional style produces visited sets using Set modules rather than mutable HashSet.

Full Source

#![allow(clippy::all)]
//! Graph - Adjacency List Representation
//!
//! Space-efficient graph representation with O(V+E) storage.

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

/// Graph with adjacency list representation
pub struct Graph {
    adj: HashMap<usize, Vec<usize>>,
    directed: bool,
}

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

    pub fn add_vertex(&mut self, v: usize) {
        self.adj.entry(v).or_default();
    }

    pub fn add_edge(&mut self, u: usize, v: usize) {
        self.adj.entry(u).or_default().push(v);
        if !self.directed {
            self.adj.entry(v).or_default().push(u);
        }
        self.adj.entry(v).or_default();
    }

    pub fn neighbors(&self, u: usize) -> &[usize] {
        self.adj.get(&u).map_or(&[], Vec::as_slice)
    }

    pub fn vertices(&self) -> impl Iterator<Item = &usize> {
        self.adj.keys()
    }

    pub fn vertex_count(&self) -> usize {
        self.adj.len()
    }

    pub fn bfs(&self, start: usize) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        let mut order = Vec::new();
        queue.push_back(start);
        visited.insert(start);
        while let Some(node) = queue.pop_front() {
            order.push(node);
            let mut neighbors: Vec<_> = self.neighbors(node).to_vec();
            neighbors.sort();
            for nb in neighbors {
                if visited.insert(nb) {
                    queue.push_back(nb);
                }
            }
        }
        order
    }

    pub fn dfs(&self, start: usize) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut stack = vec![start];
        let mut order = Vec::new();
        while let Some(node) = stack.pop() {
            if visited.insert(node) {
                order.push(node);
                let mut neighbors: Vec<_> = self.neighbors(node).to_vec();
                neighbors.sort_by(|a, b| b.cmp(a));
                for nb in neighbors {
                    if !visited.contains(&nb) {
                        stack.push(nb);
                    }
                }
            }
        }
        order
    }

    pub fn has_path(&self, from: usize, to: usize) -> bool {
        self.bfs(from).contains(&to)
    }
}

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

    #[test]
    fn test_add_edge() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        assert!(g.neighbors(0).contains(&1));
        assert!(g.neighbors(0).contains(&2));
        assert!(g.neighbors(1).contains(&0));
    }

    #[test]
    fn test_directed() {
        let mut g = Graph::new(true);
        g.add_edge(0, 1);
        assert!(g.neighbors(0).contains(&1));
        assert!(!g.neighbors(1).contains(&0));
    }

    #[test]
    fn test_bfs() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        g.add_edge(1, 3);
        g.add_edge(2, 3);
        let order = g.bfs(0);
        assert_eq!(order[0], 0);
        assert!(order.contains(&1));
        assert!(order.contains(&2));
        assert!(order.contains(&3));
    }

    #[test]
    fn test_dfs() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        g.add_edge(1, 3);
        let order = g.dfs(0);
        assert_eq!(order[0], 0);
        assert_eq!(order.len(), 4);
    }

    #[test]
    fn test_has_path() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(2, 3);
        assert!(g.has_path(0, 1));
        assert!(!g.has_path(0, 2));
    }
}

(* OCaml: graph as adjacency list *)

module G = Map.Make(Int)

let add_edge g u v =
  let lu = try G.find u g with Not_found -> [] in
  let lv = try G.find v g with Not_found -> [] in
  g |> G.add u (v::lu) |> G.add v (u::lv)

let bfs g start =
  let visited = Hashtbl.create 8 in
  let queue = Queue.create () in
  Queue.add start queue;
  Hashtbl.add visited start true;
  let order = ref [] in
  while not (Queue.is_empty queue) do
    let node = Queue.pop queue in
    order := node :: !order;
    List.iter (fun nb ->
      if not (Hashtbl.mem visited nb) then begin
        Hashtbl.add visited nb true;
        Queue.add nb queue
      end
    ) (try G.find node g with Not_found -> [])
  done;
  List.rev !order

let () =
  let g = List.fold_left (fun g (u,v) -> add_edge g u v) G.empty
    [(0,1);(0,2);(1,3);(2,3);(3,4)] in
  Printf.printf "BFS from 0: [%s]\n"
    (String.concat ";" (List.map string_of_int (bfs g 0)))

✓ Tests Rust test suite

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

    #[test]
    fn test_add_edge() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        assert!(g.neighbors(0).contains(&1));
        assert!(g.neighbors(0).contains(&2));
        assert!(g.neighbors(1).contains(&0));
    }

    #[test]
    fn test_directed() {
        let mut g = Graph::new(true);
        g.add_edge(0, 1);
        assert!(g.neighbors(0).contains(&1));
        assert!(!g.neighbors(1).contains(&0));
    }

    #[test]
    fn test_bfs() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        g.add_edge(1, 3);
        g.add_edge(2, 3);
        let order = g.bfs(0);
        assert_eq!(order[0], 0);
        assert!(order.contains(&1));
        assert!(order.contains(&2));
        assert!(order.contains(&3));
    }

    #[test]
    fn test_dfs() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        g.add_edge(1, 3);
        let order = g.dfs(0);
        assert_eq!(order[0], 0);
        assert_eq!(order.len(), 4);
    }

    #[test]
    fn test_has_path() {
        let mut g = Graph::new(false);
        g.add_edge(0, 1);
        g.add_edge(2, 3);
        assert!(g.has_path(0, 1));
        assert!(!g.has_path(0, 2));
    }
}

Deep Comparison

OCaml vs Rust: Adjacency List

Both use map/hashtable of vertex to neighbor list.

Exercises

Connected components: Implement a function that returns the number of connected components in an undirected graph using BFS/DFS, and identify which component each vertex belongs to.

Bipartite check: Write a function that determines whether a graph is bipartite (2-colorable) using BFS coloring, returning Ok((left, right)) with the two vertex sets or Err(()) if a cycle of odd length is found.

Shortest path BFS: Extend BFS to track parent pointers and reconstruct the actual path between two vertices, not just the visited order.

Open Source Repos

functional-rust

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

Rust