1037: Adjacency List Graph

Difficulty: Intermediate Category: Data Structures Concept: Graph representation using adjacency lists with BFS and DFS traversal Key Insight: `HashMap<usize, Vec<usize>>` is the natural adjacency list in Rust — sparse graphs stay memory-efficient, and `HashSet::insert()` returns `bool` making visited-tracking a one-liner.

// 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)
}

fn main() {
    test_bfs_dfs();
    test_path_finding();
    println!("✓ All tests passed");
}

#[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"

📊 Detailed 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(&[], ...)`