Rust and Data Structures

Graph Representations

A graph $G = (V, E)$ models arbitrary many-to-many relationships (edges $E$) between vertices $V$, including cycles and bidirectional links. Because arbitrary cycles violate single-owner tree semantics (Box<Node>), idiomatic Rust represents graphs using integer node indices (usize / u32) backed by contiguous vectors—avoiding Rc<RefCell<Node>> overhead while achieving superior CPU cache locality.

Directed Weighted Graph:   (0) ---[w=4]---> (1) ---[w=2]---> (2)
                            |                                 ^
                            +-------------[w=10]--------------+

1. Adjacency List (`Vec<Vec<(usize, u32)>>`):
   node 0: [ (1, 4), (2, 10) ]
   node 1: [ (2, 2) ]
   node 2: [ ]

2. Compressed Sparse Row / CSR (`offsets: Vec<usize>` + `edges: Vec<(usize, u32)>`):
   offsets: [ 0, 2, 3, 3 ]  (Node `u`'s edges live in `edges[offsets[u]..offsets[u+1]]`!)
   edges:   [ (1, 4), (2, 10), (2, 2) ]  (Single flat allocation for all edges!)

Comparing Graph Representations in Rust

Representation Rust Data Structure Memory Space Iterating Neighbors of $u$ Checking Edge $(u, v)$ Best Used For
Adjacency List Vec<Vec<Edge>> $O(|V| + |E|)$ $O(\text{deg}(u))$ $O(\text{deg}(u))$ Dynamic sparse graphs (BFS, DFS, Dijkstra, topological sort).
Compressed Sparse Row (CSR) offsets: Vec<usize> + edges: Vec<Edge> $O(|V| + |E|)$ (2 flat allocations total!) $O(\text{deg}(u))$ (Zero pointer chasing!) $O(\log(\text{deg}(u)))$ if sorted High-performance static/batch graph analytics (PageRank, routing).
Adjacency Matrix Vec<Weight> (|V| * |V|) $O(|V|^2)$ $O(|V|)$ $O(1)$ (mat[u * V + v]) Dense graphs where $|E| \approx |V|^2$ and $|V| \le 4,000$ (Floyd-Warshall).
Edge List Vec<(u32, u32, Weight)> $O(|E|)$ $O(|E|)$ $O(|E|)$ Kruskal's Minimum Spanning Tree & Bellman-Ford.

Implementing an Adjacency-List Graph with Dijkstra's Algorithm

use std::cmp::Reverse;
use std::collections::BinaryHeap;

#[derive(Debug, Clone, Copy)]
pub struct Edge {
    pub to: usize,
    pub weight: u64,
}

pub struct DiGraph {
    adj: Vec<Vec<Edge>>,
}

impl DiGraph {
    pub fn with_vertices(n: usize) -> Self {
        Self {
            adj: vec![Vec::new(); n],
        }
    }

    pub fn add_edge(&mut self, from: usize, to: usize, weight: u64) {
        self.adj[from].push(Edge { to, weight });
    }

    pub fn neighbors(&self, u: usize) -> &[Edge] {
        &self.adj[u]
    }

    /// Computes shortest path distances from `start` to all vertices using Dijkstra's algorithm.
    pub fn dijkstra(&self, start: usize) -> Vec<Option<u64>> {
        let mut dist: Vec<Option<u64>> = vec![None; self.adj.len()];
        let mut min_heap: BinaryHeap<Reverse<(u64, usize)>> = BinaryHeap::new();

        dist[start] = Some(0);
        min_heap.push(Reverse((0, start)));

        while let Some(Reverse((d, u))) = min_heap.pop() {
            if let Some(best) = dist[u] {
                if d > best {
                    continue; // Stale heap entry
                }
            }

            for &edge in self.neighbors(u) {
                let next_dist = d + edge.weight;
                if dist[edge.to].is_none_or(|cur| next_dist < cur) {
                    dist[edge.to] = Some(next_dist);
                    min_heap.push(Reverse((next_dist, edge.to)));
                }
            }
        }

        dist
    }
}

fn main() {
    let mut g = DiGraph::with_vertices(4);
    g.add_edge(0, 1, 4);
    g.add_edge(0, 2, 10);
    g.add_edge(1, 2, 2);
    g.add_edge(2, 3, 3);

    let distances = g.dijkstra(0);
    // Path 0 -> 1 -> 2 -> 3 has cost 4 + 2 + 3 = 9 (beating direct 0 -> 2 -> 3 = 13)
    assert_eq!(distances, vec![Some(0), Some(4), Some(6), Some(9)]);
    println!("Shortest distances from vertex 0: {distances:?}");
}

Shortest distances from vertex 0: [Some(0), Some(4), Some(6), Some(9)]