Graphs in Rust

Look at a metro map. It is a handful of dots joined by lines. It tells you nothing about which station is "first" or "on top". It only tells you who connects to whom.

That is a graph. The dots are called vertices (one is a vertex), and the lines are called edges. Two vertices joined by an edge are neighbours. How many neighbours a vertex has is its degree.

Some edges work both ways, like a metro track. Those graphs are undirected. Others are one-way streets, like "follows" on a social app: you can follow someone who does not follow you back. Those graphs are directed.

Linked lists and trees are graphs in disguise, with strict rules about their shape. A general graph has no rules. Any vertex may link to any other, and the links can form loops.

Reach for a graph whenever the relationships between things matter more than their order: roads between towns, friends in a network, links between web pages, or which course you must take before another. This lesson is about one question: how do you store a graph in memory? The lessons that follow will walk through them.

The trick is to give every vertex a number: 0, 1, 2, and so on. Then keep, for each vertex, a list of the numbers it is joined to. This is called an adjacency list. ("Adjacent" just means "next to".) In Rust it is a Vec of Vecs: the outer one has a slot per vertex, and each inner one is that vertex's list of neighbours.

Look at vertex 2 in the picture. Its row says [0, 1, 3], so one lookup tells you everything it touches.

There is another way to store the same map. An adjacency matrix is a square grid with one row and one column per vertex. The cell in row a, column b says true if a and b are joined.

// The same metro, as a grid: matrix[a][b] is true if a and b are joined.
let n = 5;
let mut matrix = vec![vec![false; n]; n];
for (a, b) in [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)] {
    matrix[a][b] = true;
    matrix[b][a] = true;
}

println!("{}", matrix[2][3]);
assert!(matrix[2][3]); // checking one edge is a single lookup
assert!(!matrix[0][4]);
let neighbours_of_2: Vec<usize> = (0..n).filter(|&b| matrix[2][b]).collect();
assert_eq!(neighbours_of_2, [0, 1, 3]); // but listing them scans a whole row

Asking "are 2 and 3 joined?" is one cell, so it is instant. But listing the neighbours of 2 means scanning a whole row. And the grid takes n × n cells, even if most of them say false. A graph with few edges compared with the number it could have is called sparse, and most real graphs are: nobody is friends with everyone. For those, the adjacency list is much smaller, and it is the one most people use.

There is a reason for numbers, too, and it is a very Rust reason. In lesson 7, a tree node owned its children. A graph vertex cannot work that way. Vertex 2 is a neighbour of 0, 1 and 3, and they are all neighbours of each other, so who would be the owner? Rust says every value has exactly one owner. Giving each vertex a plain number sidesteps the whole problem. A number is just a position in a Vec, and copying it costs nothing.

Remember: in Rust, a graph stores vertex numbers, not references. The numbers are indices into a Vec.

/// A graph of numbered vertices 0, 1, 2, and so on. `adj[v]` lists the
/// vertices that `v` has an edge to. A vertex is an index, never a reference.
pub struct Graph {
    adj: Vec<Vec<usize>>,
}

impl Graph {
    /// A graph with `n` vertices and no edges yet.
    pub fn new(n: usize) -> Self {
        Graph {
            adj: vec![Vec::new(); n],
        }
    }

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

    /// A two-way road: each end lists the other. Panics if a vertex is out
    /// of range, the same as indexing a `Vec` would.
    pub fn add_edge(&mut self, a: usize, b: usize) {
        self.adj[a].push(b);
        self.adj[b].push(a);
    }

    /// A one-way street: only `from` lists `to`.
    pub fn add_directed_edge(&mut self, from: usize, to: usize) {
        self.adj[from].push(to);
    }

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

    pub fn has_edge(&self, from: usize, to: usize) -> bool {
        self.adj[from].contains(&to)
    }
}

Go through it in order.

• adj is the adjacency list. vec![Vec::new(); n] makes n empty lists, one per vertex.
• add_edge adds a two-way road, so each end lists the other. add_directed_edge adds a one-way street, so only one end lists the other.
• neighbors hands back a borrowed slice of a vertex's list. The caller can read it but not change it.
• has_edge scans the list with contains. That takes as long as the list is, which is the price of this representation.
• If you pass a vertex number that is out of range, indexing panics, the same as with any Vec.

let mut metro = Graph::new(5);
metro.add_edge(0, 1);
metro.add_edge(0, 2);
metro.add_edge(1, 2);
metro.add_edge(2, 3);
metro.add_edge(3, 4);

println!("{:?}", metro.neighbors(2));
assert_eq!(metro.neighbors(2), [0, 1, 3]);
assert!(metro.has_edge(3, 4));
assert!(metro.has_edge(4, 3)); // two-way, so both directions are there

let mut one_way = Graph::new(2);
one_way.add_directed_edge(0, 1);
assert!(one_way.has_edge(0, 1));
assert!(!one_way.has_edge(1, 0));

The metro from the picture is built here. Vertex 2 has the neighbours [0, 1, 3]. The one-way graph shows the difference: 0 leads to 1, but 1 does not lead back.

A graph is only useful if you can travel across it. Here is the most common first question: how many stops away is each station? The answer comes from breadth-first search, or BFS. It visits the nearest vertices first, then the ones one step further, then one more, like ripples spreading from a stone dropped in a pond. It needs a queue, and you met one in lesson 5.

use std::collections::VecDeque;

impl Graph {
    /// How many edges lead from `start` to each vertex, or `None` if there is
    /// no way to get there. Breadth-first: nearest vertices are found first.
    pub fn distances_from(&self, start: usize) -> Vec<Option<usize>> {
        let mut dist = vec![None; self.adj.len()];
        let mut queue = VecDeque::new();
        dist[start] = Some(0);
        queue.push_back(start);

        while let Some(v) = queue.pop_front() {
            let next = dist[v].unwrap_or(0) + 1;
            for &w in &self.adj[v] {
                // `None` means "not reached yet", so each vertex is queued once.
                if dist[w].is_none() {
                    dist[w] = Some(next);
                    queue.push_back(w);
                }
            }
        }
        dist
    }
}

dist has one slot per vertex. None means "not reached yet", and Some(d) means "d stops from the start". Because of that, dist doubles as the record of where you have already been. A vertex is only queued the first time it is reached, so a loop in the graph cannot trap you.

The demo in the Playground builds a metro with six stations. Station 4 is three stops from station 0, and station 5, which has no links at all, is None.

The standard library has no Graph type, because there are too many kinds to pick one. What it does have are the parts you need:

• Vec<Vec<usize>> for the adjacency list
• VecDeque for the BFS queue
• a plain Vec as a stack, and Vec<bool> or a HashSet for "have I been here?"
• HashMap for turning names into numbers

That last one matters, because real data has names. The stations are "Central" and "Park", not 0 and 1. The usual answer is a side table that turns each name into a number once, up front.

use std::collections::HashMap;

// Vertices are numbers, so keep a table from names to numbers.
let stations = ["Central", "Park", "Market", "Harbour"];
let mut number = HashMap::new();
for (i, name) in stations.iter().enumerate() {
    number.insert(*name, i);
}

let mut adj = vec![Vec::new(); stations.len()];
for (a, b) in [("Central", "Park"), ("Park", "Market"), ("Market", "Harbour")] {
    let (a, b) = (number[a], number[b]);
    adj[a].push(b);
    adj[b].push(a);
}

// Go back from numbers to names only when you print.
let after_park: Vec<&str> = adj[number["Park"]].iter().map(|&v| stations[v]).collect();
println!("{:?}", after_park);
assert_eq!(after_park, ["Central", "Market"]);

The graph itself still holds only numbers. Names come back only at the very end, when stations[v] turns a number into text for printing. In a real project you might reach for a crate such as petgraph, which provides graph types ready made. Now you know what is inside them.

Remember: keep names in a side table, and keep the graph itself as plain numbers.

The matrix wins at "are these two joined?" and loses at nearly everything else, unless the graph is dense. The list is the sensible default.

These all take the graph as &[Vec<usize>], a borrowed adjacency list. Each starter has a signature and a todo!(), which is a placeholder that panics if it runs. Replace it with your code.

pub fn to_matrix(adj: &[Vec<usize>]) -> Vec<Vec<bool>> {
    todo!("an n by n grid, true where an edge exists")
}

pub fn to_matrix(adj: &[Vec<usize>]) -> Vec<Vec<bool>> {
    let n = adj.len();
    let mut matrix = vec![vec![false; n]; n];
    for (from, neighbors) in adj.iter().enumerate() {
        for &to in neighbors {
            matrix[from][to] = true;
        }
    }
    matrix
}

pub fn has_path(adj: &[Vec<usize>], from: usize, to: usize) -> bool {
    todo!("can you get from one vertex to the other?")
}

pub fn has_path(adj: &[Vec<usize>], from: usize, to: usize) -> bool {
    // A stack of vertices still to explore, and a note of which we have seen.
    let mut seen = vec![false; adj.len()];
    let mut stack = vec![from];
    seen[from] = true;

    while let Some(v) = stack.pop() {
        if v == to {
            return true;
        }
        for &w in &adj[v] {
            // Without `seen`, a cycle would send this round forever.
            if !seen[w] {
                seen[w] = true;
                stack.push(w);
            }
        }
    }
    false
}

pub fn count_components(adj: &[Vec<usize>]) -> usize {
    todo!("how many separate pieces is the graph in?")
}

pub fn count_components(adj: &[Vec<usize>]) -> usize {
    let mut seen = vec![false; adj.len()];
    let mut components = 0;

    for start in 0..adj.len() {
        if seen[start] {
            continue; // already part of a piece we counted
        }
        components += 1;
        // Mark everything reachable from here, so it is not counted again.
        let mut stack = vec![start];
        seen[start] = true;
        while let Some(v) = stack.pop() {
            for &w in &adj[v] {
                if !seen[w] {
                    seen[w] = true;
                    stack.push(w);
                }
            }
        }
    }
    components
}

Graph questions can look scary, because they hide in stories about islands, courses, and flights. A few habits help.

• Ask four questions first. Is it directed or undirected? Can edges have weights, such as distances? Can there be loops or repeated edges? Is it sparse or dense? The answers decide the whole approach.
• Default to an adjacency list. Mention the matrix only if the graph is dense or you need to test a single edge in O(1). Saying why shows judgement.
• Build it first. Many problems hand you a list of pairs, like [(0, 1), (1, 2)]. Turn it into an adjacency list in O(V + E) before doing anything else.
• Never forget seen. A graph can have loops, so a search without a record of visited vertices can run forever. It is the most common bug.
• Match the search to the question. Use BFS for the fewest steps, because it reaches near vertices first. Use DFS to ask "can I reach it?" or to explore everything, because the stack is quick to write.
• Say the cost in V and E. "O(V + E), since each vertex and edge is handled once" is a complete answer.
• In Rust, explain the numbers. A graph has no single owner for each vertex, so storing indices into a Vec avoids fighting the borrow checker. Mentioning the heavier alternative, Rc<RefCell<Node>>, and why you avoided it, is a strong answer.

Made by VeraStack Labs