Graphs

In chapter 11, every node had exactly one parent, and no path could lead back to where it started. A graph drops both rules. Any node can connect to any other node, and a path can come back to its start.

Graphs describe many real systems. Roads between cities form a graph. So do links between web pages, and network links between machines. Courses and their prerequisites form a graph, and so do build steps and their inputs.

The freedom has a cost. A traversal that follows edges can reach the same node many times, or walk around a loop forever. Every algorithm in this chapter therefore keeps a record of which nodes it has already handled. The record is a Vec<bool>, a HashSet, or a HashMap of states.

12.1 Graph vocabulary

Figure 12.1 names the parts of a graph.

• A node, also called a vertex, is one of the things in the graph.
• An edge connects two nodes. In a directed graph, an edge goes one way, from one node to another. In an undirected graph, an edge works both ways, like a two-way road.
• The neighbors of a node are the nodes its edges lead to.
• A weight is a number on an edge, such as a distance or a cost.
• A path is a sequence of edges that you can follow one after another.
• A cycle is a path that ends at the node where it started.

A directed graph with no cycles is called a directed acyclic graph, or DAG. A tree is a special graph: it has no cycles, and every node except the root has exactly one parent.

12.2 Storing a graph

The most common way to store a graph is an adjacency list. For every node, you keep a list of its outgoing edges. Each edge is stored as a pair: the neighbor, and the weight of the edge.

The code in this chapter uses two forms of adjacency list (figure 12.2).

In the index form, the nodes are numbered 0, 1, 2, and so on. The graph is a Vec<Vec<(usize, u32)>>. graph[i] is the list of edges out of node i, and each edge is a (neighbor, weight) pair. Finding a node’s edges is one array index. The record of visited nodes can be a Vec<bool> with one entry per node.

In the map form, nodes can be any type that can be hashed, such as names. The graph is a HashMap from a node to its edges. Finding a node’s edges means hashing the key. The visited record becomes a HashSet.

The index form is faster, and the map form is more convenient when nodes have natural names. Several files in this chapter solve the same problem both ways, so you can compare them side by side.

The map form in graph_bfs.rs has a type alias:

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

/// Adjacency list keyed by node: each node maps to its `(neighbor, weight)` edges.
pub type GraphAdjList<'a, Node> = HashMap<Node, &'a [(Node, u32)]>;

GraphAdjList<'a, Node> is a HashMap whose values are borrowed slices, &'a [(Node, u32)]. The map does not own the edges. They live somewhere else for at least the lifetime 'a, and the map points at them. The tests keep the edges in constant arrays, which live for the whole program.

12.3 Breadth-first search

Breadth-first search (BFS) visits the start node first, then every node one edge away, then every node two edges away, and so on. It works the same way as the level-order tree traversal of section 11.4: a queue holds the nodes waiting to be visited.

Unlike a tree, a graph can offer two paths to the same node. In the sample graph, A reaches C directly, and also through B. Without a record, C would enter the queue twice. So BFS marks a node as seen when it first enters the queue, and never adds it again.

The top half of figure 12.3 follows the queue step by step.

12.3.1 BFS with numbered nodes

Listing 12.1 BFS over the index form (lines 18 to 36). src/problems/graph_bfs.rs

/// BFS over an index-based adjacency list. Returns nodes in visiting order.
pub fn bfs_vec(graph: &[Vec<(usize, u32)>], start_node: usize) -> Vec<usize> {
    let mut visited = vec![false; graph.len()];
    let mut queue = VecDeque::from([start_node]);
    let mut result = vec![];

    visited[start_node] = true;

    while let Some(current_node) = queue.pop_front() {
        result.push(current_node);
        for &(neighbor, _) in &graph[current_node] {
            if !visited[neighbor] {
                visited[neighbor] = true;
                queue.push_back(neighbor);
            }
        }
    }
    result
}

The function sets up three things. visited has one false per node. queue holds the start node. result collects the nodes in the order they are visited.

The loop takes the front node, records it, and looks at its edges. The pattern &(neighbor, _) takes each edge apart: it copies out the neighbor and ignores the weight with _. Each neighbor that has not been seen is marked and added to the back of the queue.

Every node enters the queue at most once, and every edge is looked at once. So BFS runs in O(V + E) time, where V is the number of nodes and E the number of edges. Nodes that cannot be reached from the start never enter the queue, and are not in the result.

12.3.2 BFS with any node type

Listing 12.2 BFS over the map form (lines 38 to 59).

/// BFS over a `HashMap` adjacency list. Returns nodes in visiting order.
pub fn bfs<Node>(graph: &GraphAdjList<Node>, start_node: Node) -> Vec<Node>
where
    Node: Copy + Eq + Hash,
{
    let mut visited = HashSet::new();
    let mut queue = VecDeque::from([start_node]);
    let mut result = vec![];

    visited.insert(start_node);

    while let Some(current_node) = queue.pop_front() {
        result.push(current_node);
        // slice iter yields &(Node, u32); `&` destructures it
        for &(neighbor, _) in graph[&current_node] {
            if visited.insert(neighbor) {
                queue.push_back(neighbor);
            }
        }
    }
    result
}

The steps are the same. Three things change:

• The function is generic over Node. The where clause asks for Copy, so a node can be copied into the queue and the result. It also asks for Eq + Hash, so a node can be a key in a HashSet.
• graph[&current_node] looks up the edges by key. Indexing a HashMap panics if the key is missing, so every node needs an entry, even a node with no edges.
• visited.insert(neighbor) does the check and the marking in one call. insert returns true if the value was not in the set before.

The tests at the end of the file build the sample graph in both forms and check that the two functions agree:

$ cargo test --lib problems::graph_bfs
running 5 tests
test problems::graph_bfs::tests::vec_variant_skips_unreachable_nodes ... ok
test problems::graph_bfs::tests::vec_variant_visits_level_by_level ... ok
test problems::graph_bfs::tests::vec_variant_handles_cycles ... ok
test problems::graph_bfs::tests::both_variants_agree ... ok
test problems::graph_bfs::tests::map_variant_visits_level_by_level ... ok

test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 132 filtered out

Tests run in parallel, so the order of the lines can change from run to run.

12.4 Depth-first search

Depth-first search (DFS) follows one path as far as it can before it tries another. You can write it with recursion, as the tree traversals of chapter 11 were. The versions here use a Vec as an explicit stack instead. An explicit stack has no depth limit other than memory, while deep recursion can overflow the thread’s stack.

Listing 12.3 DFS over the index form (lines 16 to 33). src/problems/graph_dfs.rs

use std::{collections::HashSet, hash::Hash};

use crate::problems::graph_bfs::GraphAdjList;

/// DFS over an index-based adjacency list. Returns nodes in visiting order.
pub fn dfs_vec(graph: &[Vec<(usize, u32)>], start_node: usize) -> Vec<usize> {
    let mut visited = vec![false; graph.len()];
    let mut stack = vec![start_node];
    let mut result = vec![];

    while let Some(current_node) = stack.pop() {
        if visited[current_node] {
            continue;
        }
        visited[current_node] = true;
        result.push(current_node);
        for &(neighbor, _) in &graph[current_node] {
            stack.push(neighbor);
        }
    }
    result
}

Compare this with listing 12.1. The queue became a stack, so pop_front became pop. The other change is when a node is marked. BFS marked a node when it was added. DFS marks a node when it is taken off the stack, and skips it if it was already visited.

Marking late gives the true depth-first order, at a small cost. A node can sit on the stack more than once, as C and D do in the lower half of figure 12.3. The stack can hold up to one entry per edge, and the duplicates are skipped with continue when they come off.

The neighbors are pushed in list order, so the last neighbor pushed is the first taken. From A, the stack receives B and then C, so C is explored first. The visit order is A, C, D, B.

Listing 12.4 DFS over the map form (lines 35 to 54).

/// DFS over a `HashMap` adjacency list. Returns nodes in visiting order.
pub fn dfs<Node>(graph: &GraphAdjList<Node>, start_node: Node) -> Vec<Node>
where
    Node: Copy + Eq + Hash,
{
    let mut visited = HashSet::new();
    let mut stack = vec![start_node];
    let mut result = vec![];

    while let Some(current_node) = stack.pop() {
        if !visited.insert(current_node) {
            continue;
        }
        result.push(current_node);
        for &(neighbor, _) in graph[&current_node] {
            stack.push(neighbor);
        }
    }
    result
}

Here if !visited.insert(current_node) is the “already visited” check. If insert returns false, the node was in the set, and the loop moves on.

The file starts with use crate::problems::graph_bfs::GraphAdjList;, so both files share one type alias.

12.4.1 A stack of references

When the graph is a tree, DFS needs no visited record, because no node can be reached twice. The following program walks a tree with a stack of references.

Listing 12.5 The complete program. src/bin/rust_interview_hacks_graph.rs

#[derive(Debug)]
struct Node {
    value: i32,
    children: Vec<Node>,
}

fn visit_iter(root: &Node) {
    let mut stack = Vec::<&Node>::from([root]);

    while let Some(node) = stack.pop() {
        println!("{:?}", node);
        // Idiomatic and concise way to extend stack with neighbour iterator
        stack.extend(node.children.iter());
    }
}

fn main() {
    let tree = Node {
        value: 1,
        children: vec![
            Node {
                value: 2,
                children: vec![],
            },
            Node {
                value: 3,
                children: vec![Node {
                    value: 4,
                    children: vec![],
                }],
            },
        ],
    };

    visit_iter(&tree);
    println!("still own it: {}", tree.value); // tree wasn't moved
}

The stack has type Vec<&Node>. It holds borrowed references into the tree, so the loop moves no nodes and copies none. stack.extend(node.children.iter()) pushes a reference to each child. The last line of main uses tree.value after the walk, which shows that tree still owns its nodes.

$ cargo run --bin rust_interview_hacks_graph
Node { value: 1, children: [Node { value: 2, children: [] }, Node { value: 3, children: [Node { value: 4, children: [] }] }] }
Node { value: 3, children: [Node { value: 4, children: [] }] }
Node { value: 4, children: [] }
Node { value: 2, children: [] }
still own it: 1

{:?} prints each node with all its children, so the first line shows the whole tree. The order is 1, 3, 4, 2, because the last child pushed is the first popped.

12.5 A graph with named nodes

Programs often receive a graph as pairs of names, such as ("A", "B"). A common way to handle names is to give each name a number the first time you see it. The algorithm then runs on numbers, with the fast index form. Assigning numbers to names this way is called interning.

The graph keeps two things: ids, which interns each name as a number, and adj, the adjacency list indexed by those numbers:

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

#[derive(Default)]
struct Graph {
    ids: HashMap<String, usize>,
    adj: Vec<Vec<usize>>,
}

Listing 12.6 The complete program. src/bin/graph_bfs.rs

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

#[derive(Default)]
struct Graph {
    ids: HashMap<String, usize>,
    adj: Vec<Vec<usize>>,
}

impl Graph {
    fn id(&mut self, name: &str) -> usize {
        *self
            .ids
            .entry(name.to_owned())
            .or_insert_with(|| {
                self.adj.push(vec![]);
                self.adj.len() - 1
            })
    }

    fn add_edge(&mut self, from: &str, to: &str) {
        let (u, v) = (self.id(from), self.id(to));
        self.adj[u].push(v);
    }

    fn bfs(&self, start: &str) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut queue = VecDeque::from([self.ids[start]]);
        let mut order = Vec::new();

        while let Some(node) = queue.pop_front() {
            if !visited.insert(node) {
                continue;
            }
            order.push(node);
            queue.extend(self.adj[node].iter());
        }
        order
    }
}

fn main() {
    let mut g = Graph::default();
    g.add_edge("A", "B");
    g.add_edge("A", "C");
    g.add_edge("B", "D");
    g.add_edge("C", "E");
    g.add_edge("D", "F");

    println!("{:?}", g.bfs("A")); // [0, 1, 2, 3, 4, 5]
}

Graph has two fields. ids maps a name to its number, and adj is an index-form adjacency list without weights.

The id method does the interning in one expression. self.ids.entry(name.to_owned()) looks up the name. or_insert_with runs its closure only if the name is new. The closure adds an empty edge list to adj and returns its index, which becomes the name’s number. Either way, the expression returns a reference to the number, and the * at the front copies it out.

The closure changes self.adj while self.ids is borrowed by the entry. The compiler allows this because a closure borrows only the fields it uses, here self.adj. The two borrows touch different fields, so they do not conflict.

This bfs marks nodes when they leave the queue, as the DFS of section 12.4 did. A node can enter the queue more than once, and the second copy is skipped. queue.extend(self.adj[node].iter()) adds all neighbors at once.

$ cargo run --bin graph_bfs
[0, 1, 2, 3, 4, 5]

The result is numbers, not names. A to F were numbered 0 to 5 in the order they first appeared.

12.6 Finding cycles

Many problems need to know whether a directed graph has a cycle. A build system cannot build a file that depends on itself. A course plan cannot require a course before itself.

A visited flag is not enough to find cycles. Look at the diamond on the right of figure 12.4. DFS reaches D through B, and later reaches D again through C. That second visit does not mean there is a loop. It only means two paths join.

The fix is to give each node one of three states:

• Unvisited: DFS has not reached the node yet.
• Visiting: the node is on the path DFS is currently following. DFS has entered it and not yet finished it.
• Done: DFS has explored everything reachable from the node.

An edge that leads to a Visiting node goes back to an earlier point on the current path, so it closes a loop. Such an edge is called a back edge. An edge that leads to a Done node joins a path that was already fully explored, and cannot close a loop.

12.6.1 A graph that owns its node data

Listing 12.7 The graph and its states (lines 1 to 30). src/bin/cyclic_graph.rs

use std::collections::VecDeque;

type NodeId = usize;

struct Graph<T> {
    nodes: Vec<T>,
    adj: Vec<Vec<NodeId>>, // adj[i] = nodes that i points to
}

#[derive(Clone, Copy)]
enum State {
    Unvisited,
    Visiting,
    Done,
}

impl<T> Graph<T> {
    fn new() -> Self {
        Self {
            nodes: Vec::new(),
            adj: Vec::new(),
        }
    }

    fn add_node(&mut self, data: T) -> NodeId {
        self.nodes.push(data);
        self.adj.push(Vec::new());
        self.nodes.len() - 1
    }

    fn add_edge(&mut self, from: NodeId, to: NodeId) {
        self.adj[from].push(to);
    }

    fn neighbors(&self, id: NodeId) -> impl Iterator<Item = NodeId> + '_ {
        self.adj[id].iter().copied()
    }
    // ...
}

This Graph<T> keeps the node data in nodes, and the edges in adj, as numbers. NodeId is a type alias for usize, so signatures say what a number means. add_node returns the new node’s number, and the caller uses that number to add edges.

Storing numbers instead of references is the usual way to build graphs in Rust. A cycle of references between nodes would need Rc and RefCell, as chapter 9’s doubly linked list did. Numbers into a Vec have no ownership problems at all.

neighbors returns impl Iterator<Item = NodeId> + '_. That return type means “some iterator of node numbers”. The + '_ says the iterator borrows from self, so it cannot outlive the graph. .copied() turns the &usize items of the slice iterator into usize values.

Listing 12.8 BFS and DFS (lines 39 to 74).

impl<T> Graph<T> {
    // ...
    fn bfs(&self, start: NodeId) -> Vec<NodeId> {
        let mut visited = vec![false; self.nodes.len()];
        let mut queue = VecDeque::from([start]);
        let mut order = Vec::new();
        visited[start] = true;

        while let Some(node) = queue.pop_front() {
            order.push(node);
            for next in self.neighbors(node) {
                if !visited[next] {
                    visited[next] = true;
                    queue.push_back(next);
                }
            }
        }
        order
    }

    fn dfs(&self, start: NodeId) -> Vec<NodeId> {
        let mut visited = vec![false; self.nodes.len()];
        let mut stack = vec![start];
        let mut order = Vec::new();

        while let Some(node) = stack.pop() {
            if visited[node] {
                continue;
            }
            visited[node] = true;
            order.push(node);
            stack.extend(
                self.neighbors(node)
                    .filter(|&n| !visited[n]),
            );
        }
        order
    }
    // ...
}

These are the algorithms of sections 12.3 and 12.4, written with neighbors. The DFS filters out visited neighbors before pushing them, with .filter(|&n| !visited[n]). The filter keeps the stack smaller, but the check after pop is still needed. A node can be pushed by two different nodes before either copy is popped.

Listing 12.9 Cycle detection (lines 76 to 94).

impl<T> Graph<T> {
    // ...
    fn has_cycle(&self) -> bool {
        let mut state = vec![State::Unvisited; self.nodes.len()];
        (0..self.nodes.len()).any(|n| self.visit(n, &mut state))
    }

    fn visit(&self, node: NodeId, state: &mut [State]) -> bool {
        match state[node] {
            State::Visiting => true, // back edge: cycle found
            State::Done => false,
            State::Unvisited => {
                state[node] = State::Visiting;
                let found = self.adj[node]
                    .iter()
                    .any(|&n| self.visit(n, state));
                state[node] = State::Done;
                found
            }
        }
    }
}

visit is a recursive DFS that returns true as soon as it finds a cycle. It reads the node’s state:

• Visiting means this edge is a back edge, so the answer is true.
• Done means the node was explored before and no cycle was found through it, so the answer is false.
• Unvisited means this is the first visit. The node becomes Visiting, and visit recurses into each neighbor. any stops at the first neighbor that reports a cycle. Then the node becomes Done.

has_cycle calls visit from every node, because a cycle might not be reachable from node 0. All the calls share one state vector, so each node is fully explored only once, and the whole check runs in O(V + E).

Listing 12.10 The complete program. src/bin/cyclic_graph.rs

use std::collections::VecDeque;

type NodeId = usize;

struct Graph<T> {
    nodes: Vec<T>,
    adj: Vec<Vec<NodeId>>, // adj[i] = nodes that i points to
}

#[derive(Clone, Copy)]
enum State {
    Unvisited,
    Visiting,
    Done,
}

impl<T> Graph<T> {
    fn new() -> Self {
        Self {
            nodes: Vec::new(),
            adj: Vec::new(),
        }
    }

    fn add_node(&mut self, data: T) -> NodeId {
        self.nodes.push(data);
        self.adj.push(Vec::new());
        self.nodes.len() - 1
    }

    fn add_edge(&mut self, from: NodeId, to: NodeId) {
        self.adj[from].push(to);
    }

    fn neighbors(&self, id: NodeId) -> impl Iterator<Item = NodeId> + '_ {
        self.adj[id].iter().copied()
    }

    fn bfs(&self, start: NodeId) -> Vec<NodeId> {
        let mut visited = vec![false; self.nodes.len()];
        let mut queue = VecDeque::from([start]);
        let mut order = Vec::new();
        visited[start] = true;

        while let Some(node) = queue.pop_front() {
            order.push(node);
            for next in self.neighbors(node) {
                if !visited[next] {
                    visited[next] = true;
                    queue.push_back(next);
                }
            }
        }
        order
    }

    fn dfs(&self, start: NodeId) -> Vec<NodeId> {
        let mut visited = vec![false; self.nodes.len()];
        let mut stack = vec![start];
        let mut order = Vec::new();

        while let Some(node) = stack.pop() {
            if visited[node] {
                continue;
            }
            visited[node] = true;
            order.push(node);
            stack.extend(
                self.neighbors(node)
                    .filter(|&n| !visited[n]),
            );
        }
        order
    }

    fn has_cycle(&self) -> bool {
        let mut state = vec![State::Unvisited; self.nodes.len()];
        (0..self.nodes.len()).any(|n| self.visit(n, &mut state))
    }

    fn visit(&self, node: NodeId, state: &mut [State]) -> bool {
        match state[node] {
            State::Visiting => true, // back edge: cycle found
            State::Done => false,
            State::Unvisited => {
                state[node] = State::Visiting;
                let found = self.adj[node]
                    .iter()
                    .any(|&n| self.visit(n, state));
                state[node] = State::Done;
                found
            }
        }
    }
}

fn main() {
    let mut g = Graph::new();
    let a = g.add_node("A");
    let b = g.add_node("B");
    let c = g.add_node("C");

    g.add_edge(a, b);
    g.add_edge(b, c);
    g.add_edge(c, a); // closes the cycle

    let names = |ids: Vec<NodeId>| -> Vec<&str> {
        ids.into_iter()
            .map(|i| g.nodes[i])
            .collect()
    };

    println!("BFS:   {:?}", names(g.bfs(a))); // ["A", "B", "C"]
    println!("DFS:   {:?}", names(g.dfs(a))); // ["A", "B", "C"]
    println!("Cycle: {}", g.has_cycle()); // true
}

main builds the loop A to B to C to A. The closure names converts a list of numbers back into names for printing.

$ cargo run --bin cyclic_graph
BFS:   ["A", "B", "C"]
DFS:   ["A", "B", "C"]
Cycle: true

12.6.2 The same graph with a HashMap

The second version stores the graph as a map from a node to its neighbors, with no numbering step.

The cycle check marks each node with a State: Visiting while its descendants are being explored, and Done after. The graph is a map from a node to its neighbors, generic over any Copy node type:

#[derive(Clone, Copy)]
enum State {
    Visiting,
    Done,
}

#[derive(Default)]
struct Graph<T> {
    adj: HashMap<T, Vec<T>>,
}

Listing 12.11 The complete program. src/bin/cyclic_graph_map.rs

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

#[derive(Clone, Copy)]
enum State {
    Visiting,
    Done,
}

#[derive(Default)]
struct Graph<T> {
    adj: HashMap<T, Vec<T>>,
}

impl<T: Copy + Eq + Hash> Graph<T> {
    fn add_edge(&mut self, u: T, v: T) {
        self.adj.entry(v).or_default();
        self.adj.entry(u).or_default().push(v);
    }

    fn bfs(&self, start: T) -> Vec<T> {
        let mut seen = HashSet::from([start]);
        let mut queue = VecDeque::from([start]);
        let mut order = vec![];

        while let Some(u) = queue.pop_front() {
            order.push(u);
            for &v in &self.adj[&u] {
                if seen.insert(v) {
                    queue.push_back(v);
                }
            }
        }
        order
    }

    fn has_cycle(&self) -> bool {
        fn dfs<T: Copy + Eq + Hash>(g: &Graph<T>, u: T, state: &mut HashMap<T, State>) -> bool {
            match state.get(&u) {
                Some(State::Visiting) => return true,
                Some(State::Done) => return false,
                None => {}
            }

            state.insert(u, State::Visiting);
            let found = g.adj[&u]
                .iter()
                .any(|&v| dfs(g, v, state));
            state.insert(u, State::Done);
            found
        }

        let mut state = HashMap::new();
        self.adj
            .keys()
            .any(|&u| dfs(self, u, &mut state))
    }
}

fn main() {
    let mut g = Graph::default();
    g.add_edge("A", "B");
    g.add_edge("B", "C");
    g.add_edge("C", "A");

    println!("{:?}", g.bfs("A"));
    println!("{}", g.has_cycle()); // true
}

Three details differ from listing 12.10:

• State has only Visiting and Done. A node that is not in the state map is unvisited, so the map itself plays the role of the third state.
• add_edge inserts the target v as a key too, with entry(v).or_default(). Every node therefore has an entry, and self.adj[&u] cannot panic on a node that has no outgoing edges.
• The recursive helper is a function declared inside has_cycle. A nested fn cannot use the local variables of the function around it, so it receives the graph and the state map as arguments.

$ cargo run --bin cyclic_graph_map
["A", "B", "C"]
true

12.7 A grid is a graph

A grid of cells is a graph too, even though it is not stored as one. Each cell is a node, and each cell has an edge to the cells directly above, below, left, and right of it. The edges are computed from the coordinates when needed, not stored.

The classic grid problem counts islands. The grid holds land and water. An island is a group of land cells connected up, down, left, or right. Diagonal neighbors do not count.

The method is to scan every cell. When the scan finds a land cell that no earlier search has reached, that cell starts a new island. The count goes up by one, and a BFS from that cell marks every cell of the island. Filling a connected area this way is called a flood fill (figure 12.5).

Listing 12.12 Counting islands (lines 27 to 72). src/bin/count_islands.rs

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

fn count_islands<T: PartialEq>(grid: &[&[T]], land: T) -> usize {
    if grid.is_empty() || grid[0].is_empty() {
        return 0;
    }

    let rows = grid.len();
    let cols = grid[0].len();
    let mut visited = HashSet::new();
    let mut count = 0;
    let dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)];

    // BFS closure: flood-fill one island starting from a known land cell.
    // Passing `visited` explicitly avoids borrow-checker friction when calling
    // the closure from the outer loop.
    let bfs = |start: (usize, usize), visited: &mut HashSet<(usize, usize)>| {
        let mut queue = VecDeque::new();
        queue.push_back(start);
        visited.insert(start);

        while let Some((cr, cc)) = queue.pop_front() {
            for &(dr, dc) in &dirs {
                let nr = cr as i32 + dr;
                let nc = cc as i32 + dc;

                if (0..rows as i32).contains(&nr) && (0..cols as i32).contains(&nc) {
                    let (ur, uc) = (nr as usize, nc as usize);
                    if grid[ur][uc] == land && !visited.contains(&(ur, uc)) {
                        visited.insert((ur, uc));
                        queue.push_back((ur, uc));
                    }
                }
            }
        }
    };

    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] == land && !visited.contains(&(r, c)) {
                count += 1;
                bfs((r, c), &mut visited);
            }
        }
    }

    count
}

The grid has type &[&[T]], a slice of rows, where each row is a slice of cells. The function is generic, so cells can be characters, booleans, or numbers. land: T says which value counts as land, and T: PartialEq lets the code compare a cell with it.

dirs lists the four moves as (row change, column change) pairs. The BFS adds each move to the current cell’s coordinates. The coordinates are usize, which cannot be negative, and a move up from row 0 would go below zero. So the code converts to i32 first. It checks that the new position is inside the grid with (0..rows as i32).contains(&nr), and only then converts back to usize.

The BFS is a closure stored in bfs. It reads grid, dirs, rows, cols, and land from the function around it. It does not capture visited, though. It takes visited as a parameter instead. If the closure captured visited mutably, that borrow would last as long as the closure. The outer loop could then not call visited.contains while the closure exists. Passing it in on each call keeps the borrow short.

Each cell is looked at a constant number of times, so the function runs in O(rows × cols). A Vec<bool> with one entry per cell would be faster than the HashSet of coordinates, because it avoids hashing.

Listing 12.13 The complete program, with tests. src/bin/count_islands.rs

// ============================================================================
// Count Islands
//
// Ported from the Rust playground repo.
//
// Problem: given a grid of cells, count the number of connected "land"
// regions. Two land cells are connected when they are adjacent horizontally
// or vertically (4-directional). Water cells are not traversable.
//
// Where this shape appears in practice:
//   - "Islands" are connected-component counting, the same shape used to find
//     connected machines, failure domains, network partitions, or storage
//     groups in distributed systems.
//   - The generic implementation accepts any land type (char, u8, bool) and
//     uses BFS with an explicit visited set, which is easy to reason about.
//
// Time complexity: O(rows * cols)
// Space complexity: O(rows * cols) for the visited set and BFS queue.
// ============================================================================

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

/// Counts 4-directionally connected components of `land` in a rectangular grid.
///
/// The grid is generic over cell values so callers can use `'1'/'0'`,
/// `true/false`, `1u8/0u8`, or any other PartialEq value.
fn count_islands<T: PartialEq>(grid: &[&[T]], land: T) -> usize {
    if grid.is_empty() || grid[0].is_empty() {
        return 0;
    }

    let rows = grid.len();
    let cols = grid[0].len();
    let mut visited = HashSet::new();
    let mut count = 0;
    let dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)];

    // BFS closure: flood-fill one island starting from a known land cell.
    // Passing `visited` explicitly avoids borrow-checker friction when calling
    // the closure from the outer loop.
    let bfs = |start: (usize, usize), visited: &mut HashSet<(usize, usize)>| {
        let mut queue = VecDeque::new();
        queue.push_back(start);
        visited.insert(start);

        while let Some((cr, cc)) = queue.pop_front() {
            for &(dr, dc) in &dirs {
                let nr = cr as i32 + dr;
                let nc = cc as i32 + dc;

                if (0..rows as i32).contains(&nr) && (0..cols as i32).contains(&nc) {
                    let (ur, uc) = (nr as usize, nc as usize);
                    if grid[ur][uc] == land && !visited.contains(&(ur, uc)) {
                        visited.insert((ur, uc));
                        queue.push_back((ur, uc));
                    }
                }
            }
        }
    };

    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] == land && !visited.contains(&(r, c)) {
                count += 1;
                bfs((r, c), &mut visited);
            }
        }
    }

    count
}

// ============================================================================
// Runnable demonstration
// ============================================================================
fn main() {
    let grid = [
        &['1', '1', '0', '0', '0'][..],
        &['1', '1', '0', '0', '0'][..],
        &['0', '0', '1', '0', '0'][..],
        &['0', '0', '0', '1', '1'][..],
    ];

    println!("Islands: {}", count_islands(&grid, '1'));

    let boolean_grid = [
        &[true, true, false][..],
        &[false, false, false][..],
        &[false, true, true][..],
    ];
    println!("Boolean islands: {}", count_islands(&boolean_grid, true));
}

// ============================================================================
// Tests (cargo test --bin count_islands)
// ============================================================================
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_grid_has_zero_islands() {
        let empty: [&[char]; 0] = [];
        assert_eq!(count_islands(&empty, '1'), 0);

        let no_cols: [&[char]; 2] = [&[], &[]];
        assert_eq!(count_islands(&no_cols, '1'), 0);
    }

    #[test]
    fn counts_classic_example() {
        let grid = [
            &['1', '1', '0', '0', '0'][..],
            &['1', '1', '0', '0', '0'][..],
            &['0', '0', '1', '0', '0'][..],
            &['0', '0', '0', '1', '1'][..],
        ];
        assert_eq!(count_islands(&grid, '1'), 3);
    }

    #[test]
    fn all_water_is_zero() {
        let grid = [&['0', '0'][..], &['0', '0'][..]];
        assert_eq!(count_islands(&grid, '1'), 0);
    }

    #[test]
    fn generic_bool_grid_works() {
        let grid = [
            &[true, false, false][..],
            &[true, false, true][..],
            &[false, false, true][..],
        ];
        assert_eq!(count_islands(&grid, true), 2);
    }

    #[test]
    fn single_row_and_column() {
        let row = [&['1', '0', '1', '1'][..]];
        assert_eq!(count_islands(&row, '1'), 2);

        let col = [&['1'][..], &['1'][..], &['0'][..], &['1'][..]];
        assert_eq!(count_islands(&col, '1'), 2);
    }
}

$ cargo run --bin count_islands
Islands: 3
Boolean islands: 2

$ cargo test --bin count_islands
running 5 tests
test tests::empty_grid_has_zero_islands ... ok
test tests::all_water_is_zero ... ok
test tests::generic_bool_grid_works ... ok
test tests::single_row_and_column ... ok
test tests::counts_classic_example ... ok

test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

12.8 Putting tasks in order

Suppose you have tasks, and some tasks must finish before others can start. A topological order lists every task so that each one comes after all of its prerequisites. Build tools, package managers, and course planners all compute one.

Draw an arrow from each task to the tasks that depend on it. The indegree of a node is the number of arrows coming into it: the number of prerequisites it is still waiting for.

Kahn’s algorithm builds the order step by step (figure 12.6):

1. Put every node with indegree 0 in a queue. They have no prerequisites.
2. Take a node from the queue and add it to the order.
3. For each arrow out of that node, lower the target’s indegree by one. The target has one fewer prerequisite to wait for. If its indegree reaches 0, add it to the queue.
4. Repeat until the queue is empty.

If the graph has a cycle, the nodes on the cycle wait for each other forever. Their indegrees never reach 0, so they never enter the order. The order then comes out shorter than the number of nodes, and that is how the algorithm detects a cycle.

12.8.1 Kahn’s algorithm on numbered nodes

The input is a node count and a slice of (from, to) edges. The first step builds the adjacency list and counts each node’s indegree at the same time:

use std::collections::VecDeque;

pub fn topological_sort(num_nodes: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut graph = vec![Vec::new(); num_nodes];
    let mut indegree = vec![0usize; num_nodes];

    for &(from, to) in edges {
        graph[from].push(to);
        indegree[to] += 1;
    }
    // ...
}

The starting queue comes from one iterator chain:

pub fn topological_sort(num_nodes: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    // ...
    let mut queue: VecDeque<usize> = (0..num_nodes)
        .filter(|&n| indegree[n] == 0)
        .collect();
    let mut order = Vec::with_capacity(num_nodes);
    // ...
}

(0..num_nodes) produces every node number. .filter(|&n| indegree[n] == 0) keeps the nodes with no prerequisites, and .collect() builds the VecDeque.

The loop is Kahn’s algorithm itself:

pub fn topological_sort(num_nodes: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    // ...
    while let Some(node) = queue.pop_front() {
        order.push(node);

        for &next in &graph[node] {
            indegree[next] -= 1;
            if indegree[next] == 0 {
                queue.push_back(next);
            }
        }
    }

    (order.len() == num_nodes).then_some(order)
}

Each node taken from the queue goes into order. Removing it removes its outgoing edges, so each neighbor’s indegree drops by one. A neighbor whose indegree reaches 0 has no prerequisites left, and joins the queue.

The last line returns the answer. bool::then_some(order) gives Some(order) if the condition is true, and None if it is false. So the function returns None exactly when a cycle kept some nodes out of the order. The nodes on a cycle never reach indegree 0.

Listing 12.14 The complete file. src/problems/graph_topology.rs

//! Topological sort (Kahn's algorithm).
//!
//! Common in scheduling problems: prerequisite graphs, pipeline
//! stages, and build or job dependency ordering.

use std::collections::VecDeque;

pub fn topological_sort(num_nodes: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut graph = vec![Vec::new(); num_nodes];
    let mut indegree = vec![0usize; num_nodes];

    for &(from, to) in edges {
        graph[from].push(to);
        indegree[to] += 1;
    }

    let mut queue: VecDeque<usize> = (0..num_nodes)
        .filter(|&n| indegree[n] == 0)
        .collect();
    let mut order = Vec::with_capacity(num_nodes);

    while let Some(node) = queue.pop_front() {
        order.push(node);

        for &next in &graph[node] {
            indegree[next] -= 1;
            if indegree[next] == 0 {
                queue.push_back(next);
            }
        }
    }

    (order.len() == num_nodes).then_some(order)
}

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

    #[test]
    fn returns_order_for_dag() {
        // 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3
        let edges = [(0, 1), (0, 2), (1, 3), (2, 3)];
        let order = topological_sort(4, &edges).expect("DAG has an order");
        assert_eq!(order.len(), 4);
        assert!(
            order
                .iter()
                .position(|&n| n == 0)
                .unwrap()
                < order
                    .iter()
                    .position(|&n| n == 1)
                    .unwrap()
        );
        assert!(
            order
                .iter()
                .position(|&n| n == 1)
                .unwrap()
                < order
                    .iter()
                    .position(|&n| n == 3)
                    .unwrap()
        );
    }

    #[test]
    fn detects_cycle() {
        // 0 -> 1 -> 0 is a cycle.
        let edges = [(0, 1), (1, 0)];
        assert_eq!(topological_sort(2, &edges), None);
    }

    #[test]
    fn disconnected_nodes_are_included() {
        let edges = [(0, 1)];
        let order = topological_sort(3, &edges).expect("DAG has an order");
        assert_eq!(order.len(), 3);
    }
}

The tests check positions rather than one exact order. A graph usually has several valid topological orders, and the tests only require that each edge’s source comes before its target.

$ cargo test --lib problems::graph_topology
running 3 tests
test problems::graph_topology::tests::disconnected_nodes_are_included ... ok
test problems::graph_topology::tests::returns_order_for_dag ... ok
test problems::graph_topology::tests::detects_cycle ... ok

test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 134 filtered out

12.8.2 Kahn’s algorithm on named courses

The second version takes courses with names and lists of prerequisites, the way the data might arrive from a file.

A course has a name and a list of prerequisites, the names of the courses that must come before it:

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

#[derive(Clone)]
struct Course {
    name: String,
    depends_on: Vec<String>,
}

Listing 12.15 The complete program. src/bin/dependency_resolutiom.rs

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

#[derive(Clone)]
struct Course {
    name: String,
    depends_on: Vec<String>,
}

fn topo_sort(courses: &[Course]) -> Vec<String> {
    let mut adj: HashMap<String, Vec<String>> = HashMap::new();
    let mut indegree: HashMap<String, usize> = HashMap::new();

    for Course { name, depends_on } in courses {
        indegree.insert(name.clone(), depends_on.len());
        adj.entry(name.clone()).or_default();
        for dep in depends_on {
            adj.entry(dep.clone())
                .or_default()
                .push(name.clone());
            indegree.entry(dep.clone()).or_insert(0);
        }
    }

    let mut queue: VecDeque<_> = indegree
        .iter()
        .filter(|&(_, deg)| *deg == 0)
        .map(|(name, _)| name.clone())
        .collect();

    let mut order = Vec::new();
    while let Some(node) = queue.pop_front() {
        for next in &adj[&node] {
            let d = indegree.get_mut(next).unwrap();
            *d -= 1;
            if *d == 0 {
                queue.push_back(next.clone());
            }
        }
        order.push(node);
    }

    if order.len() == indegree.len() {
        order
    } else {
        Vec::new()
    }
}

fn main() {
    let courses = vec![
        Course {
            name: "algos".into(),
            depends_on: vec!["datastructs".into()],
        },
        Course {
            name: "compilers".into(),
            depends_on: vec!["algos".into(), "os".into()],
        },
        Course {
            name: "os".into(),
            depends_on: vec!["datastructs".into()],
        },
    ];

    println!("{:?}", topo_sort(&courses));
}

The input describes edges backward from the way the algorithm needs them. Each course lists its prerequisites, but Kahn’s algorithm follows arrows from a prerequisite to the courses that need it. The loop turns them around. For each prerequisite dep of course name, it adds name to adj[dep].

A course’s indegree is the length of its depends_on list. A prerequisite that is never listed as a course, like datastructs here, still needs an entry. indegree.entry(dep.clone()).or_insert(0) adds it with indegree 0, and or_insert leaves an existing entry alone.

for Course { name, depends_on } in courses takes each course apart in the loop header. Because courses is a slice reference, name and depends_on are references to the fields.

If a cycle keeps some courses out of the order, the function returns an empty Vec. With Option as in listing 12.14, the caller could tell “no courses” from “a cycle”.

$ cargo run --bin dependency_resolutiom
["datastructs", "algos", "os", "compilers"]

The starting queue is built by iterating over a HashMap, and that order changes between runs. This input has only one course with no prerequisites, so the output is always the same. With several such courses, the order among them could change from run to run.

12.9 Shortest paths

In a weighted graph, the cost of a path is the sum of its edge weights. The shortest path from A to D is the path with the lowest cost. It is not always the one with the fewest edges.

BFS finds the path with the fewest edges, which is a different question. Dijkstra’s algorithm finds the lowest cost from one start node to every other node, as long as no weight is negative.

12.9.1 How Dijkstra’s algorithm works

The algorithm keeps two things:

• dist, the lowest cost found so far to each node. At the start, only the start node has a cost, 0.
• A min-heap of (cost, node) entries, so the cheapest entry is always taken next. Chapter 5 built min-heaps with BinaryHeap and Reverse.

Each step takes the cheapest entry from the heap. For each edge out of that node, it computes the cost of reaching the neighbor through this node. If that cost beats the neighbor’s recorded cost, the new cost is recorded and pushed onto the heap. Updating a recorded cost to a lower one is called relaxing the edge.

When a node is taken from the heap with its recorded cost, that cost is final. Every other entry in the heap costs at least as much, and weights are never negative. So no path found later can come back cheaper.

A node can be in the heap several times. When a cheaper path to B is found, the old entry for B stays in the heap. BinaryHeap has no way to find and update it. When the old entry is eventually taken, its cost is higher than B’s recorded cost, and the code skips it. Such an entry is called stale.

Figure 12.7 follows every step on a four-node graph.

Read the table row by row. Taking A records B at 4 and C at 1. Taking C finds B at 1 + 2 = 3, which beats 4, so B is recorded at 3 and pushed again. The old (4, B) entry is now stale. Taking B at 3 finds D at 4, which beats the 6 recorded through C. Later, (4, B) and (6, D) come off the heap, and each is skipped because its cost is higher than the recorded one.

12.9.2 Two versions side by side

Listing 12.16 Dijkstra over the index form (lines 23 to 44). src/problems/graph_dijkstra.rs

use std::{
    cmp::Reverse,
    collections::{BinaryHeap, HashMap},
    hash::Hash,
};

use crate::problems::graph_bfs::GraphAdjList;

/// Shortest distances from `start_node` over an index-based adjacency list.
pub fn dijkstra_vec(graph: &[Vec<(usize, u32)>], start_node: usize) -> Vec<Option<u32>> {
    let mut distances = vec![None; graph.len()];
    let mut min_heap = BinaryHeap::from([Reverse((0, start_node))]);

    distances[start_node] = Some(0);

    while let Some(Reverse((current_cost, current_node))) = min_heap.pop() {
        // stale heap entry, a shorter path was already recorded
        if distances[current_node].is_some_and(|best| current_cost > best) {
            continue;
        }
        for &(neighbor, weight) in &graph[current_node] {
            let new_distance = current_cost + weight;
            if distances[neighbor].is_none_or(|best| new_distance < best) {
                distances[neighbor] = Some(new_distance);
                min_heap.push(Reverse((new_distance, neighbor)));
            }
        }
    }
    distances
}

The distances are a Vec<Option<u32>>, where None means “no path found yet”. Two methods of Option read well here:

• is_some_and(|best| current_cost > best) is true only if there is a recorded cost and the popped cost is higher. That is the stale check.
• is_none_or(|best| new_distance < best) is true if there is no recorded cost, or the new cost is lower. That is the relax check.

The heap holds Reverse((cost, node)). BinaryHeap pops the largest item, and Reverse flips the comparison, so the smallest cost comes out first. Tuples compare by their first field, then by their second, so the cost decides and the node number breaks ties.

Listing 12.17 Dijkstra over the map form (lines 46 to 73).

/// Shortest distances from `start_node` over a `HashMap` adjacency list.
pub fn dijkstra<Node>(graph: &GraphAdjList<Node>, start_node: Node) -> HashMap<Node, u32>
where
    Node: Copy + Eq + Hash + Ord,
{
    let mut distances = HashMap::from([(start_node, 0)]);
    let mut min_heap = BinaryHeap::from([Reverse((0, start_node))]);

    while let Some(Reverse((current_cost, current_node))) = min_heap.pop() {
        // stale heap entry, a shorter path was already recorded
        if current_cost > distances[&current_node] {
            continue;
        }
        for &(neighbor, weight) in graph[&current_node] {
            let new_distance = current_cost + weight;

            if new_distance
                < *distances
                    .get(&neighbor)
                    .unwrap_or(&u32::MAX)
            {
                distances.insert(neighbor, new_distance);
                min_heap.push(Reverse((new_distance, neighbor)));
            }
        }
    }
    distances
}

In this version, distances is a HashMap that contains only nodes that have been reached. Node also needs Ord, because nodes sit inside the tuples that the heap compares.

distances[&current_node] cannot panic here. A node is pushed onto the heap only after its distance is inserted, so every popped node has an entry. distances.get(&neighbor).unwrap_or(&u32::MAX) treats a missing entry as the largest possible cost, so any real cost beats it.

Each edge can push one heap entry, and each heap operation takes O(log E). The whole algorithm runs in O(E log E), which is the same as O(E log V) for simple graphs.

$ cargo test --lib problems::graph_dijkstra
running 4 tests
test problems::graph_dijkstra::tests::vec_variant_finds_shorter_multi_hop_paths ... ok
test problems::graph_dijkstra::tests::vec_variant_marks_unreachable_nodes ... ok
test problems::graph_dijkstra::tests::map_variant_omits_unreachable_nodes ... ok
test problems::graph_dijkstra::tests::map_variant_finds_shorter_multi_hop_paths ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 133 filtered out

12.9.3 Edges as a struct

The next three programs use a named Edge struct instead of a (neighbor, weight) tuple, and u64 costs. They show three steps of the same function: it first clones node names, then borrows them, and finally handles missing nodes and overflow.

An Edge holds the node it leads to and its weight. AdjMap is an alias for the graph: each node, with the list of edges that leave it. Both are generic over the node type:

#[derive(Debug)]
struct Edge<Node> {
    to: Node,
    weight: u64,
}

type AdjMap<Node> = HashMap<Node, Vec<Edge<Node>>>;

Listing 12.18 The complete program. src/bin/dijkstra.rs

use std::{
    cmp::Reverse,
    collections::{BinaryHeap, HashMap},
    hash::Hash,
};

#[derive(Debug)]
struct Edge<Node> {
    to: Node,
    weight: u64,
}

type AdjMap<Node> = HashMap<Node, Vec<Edge<Node>>>;

fn dijkstra_ssmd_shortest<Node>(graph: &AdjMap<Node>, start: Node) -> HashMap<Node, u64>
where
    Node: Clone + Hash + Ord,
{
    let mut dist = HashMap::from([(start.clone(), 0)]);
    let mut heap = BinaryHeap::from([Reverse((0, start))]);

    while let Some(Reverse((cost, node))) = heap.pop() {
        if cost > dist[&node] {
            continue; // stale entry
        }
        for edge in &graph[&node] {
            let new_cost = cost + edge.weight;
            if dist
                .get(&edge.to)
                .is_none_or(|&d| new_cost < d)
            {
                dist.insert(edge.to.clone(), new_cost);
                heap.push(Reverse((new_cost, edge.to.clone())));
            }
        }
    }
    dist
}

fn main() {
    let graph: AdjMap<&str> = HashMap::from([
        (
            "A",
            vec![Edge { to: "B", weight: 4 }, Edge { to: "C", weight: 1 }],
        ),
        ("B", vec![Edge { to: "D", weight: 1 }]),
        (
            "C",
            vec![Edge { to: "B", weight: 2 }, Edge { to: "D", weight: 5 }],
        ),
        ("D", vec![]),
    ]);

    println!("{:#?}", graph);
    let dist = dijkstra_ssmd_shortest(&graph, "A");
    println!("{:#?}", dist); // {"A": 0, "C": 1, "B": 3, "D": 4} (order varies)
}

edge.to and edge.weight read better than .0 and .1. The node type needs Clone instead of Copy, so it could be a String. The function clones a node each time it stores one in dist or on the heap.

graph[&node] panics if a node has no entry in the map. main includes "D" with an empty list, so every node has one.

$ cargo run --bin dijkstra
{
    "B": [
        Edge {
            to: "D",
            weight: 1,
        },
    ],
    ...
}
{
    "B": 3,
    "C": 1,
    "A": 0,
    "D": 4,
}

The first print shows the graph and is cut short here. A HashMap does not keep its entries in any order. The lines of both prints can come out in a different order on your machine.

Listing 12.19 The graph types, and borrowing nodes instead of cloning them (lines 1 to 47). src/bin/dijkstra_with_lifetime.rs

use std::{
    cmp::Reverse,
    collections::{BinaryHeap, HashMap},
    hash::Hash,
};

#[derive(Debug)]
struct Edge<Node> {
    to: Node,
    weight: u64,
}

type AdjMap<Node> = HashMap<Node, Vec<Edge<Node>>>;

fn dijkstra_ssmd_shortest<'a, Node>(
    graph: &'a AdjMap<Node>,
    start: &'a Node,
) -> HashMap<&'a Node, u64>
where
    Node: Hash + Ord,
{
    let mut dist = HashMap::from([(start, 0u64)]);
    let mut heap = BinaryHeap::from([Reverse((0u64, start))]);

    while let Some(Reverse((cost, node))) = heap.pop() {
        if cost > dist[node] {
            continue; // stale entry
        }
        let Some(edges) = graph.get(node) else {
            continue;
        };

        for edge in edges {
            let Some(new_cost) = cost.checked_add(edge.weight) else {
                continue;
            };
            if dist
                .get(&edge.to)
                .is_none_or(|&d| new_cost < d)
            {
                dist.insert(&edge.to, new_cost);
                heap.push(Reverse((new_cost, &edge.to)));
            }
        }
    }
    dist
}

The types are generic over Node, the type that names a node, such as &str or u32. An Edge<Node> holds the node it leads to and a weight. AdjMap<Node> is an alias for the adjacency map: each node, and the list of edges that leave it.

This version stores references to nodes, &'a Node, in dist and in the heap, so Node does not need Clone. With String nodes, that saves an allocation per clone.

The lifetime 'a ties everything together. The graph and the start node are both borrowed for 'a, and the returned map holds &'a Node keys. The compiler therefore keeps the graph alive as long as the result is in use. Every reference pushed onto the heap, &edge.to, points into the graph, so it lives long enough.

Two let ... else lines make the function safer than listing 12.18:

• let Some(edges) = graph.get(node) else { continue }; handles a node that has no entry in the map. main leaves "D" out of the map, and the function still works.
• let Some(new_cost) = cost.checked_add(edge.weight) else { continue }; skips an edge whose total cost would overflow. checked_add returns None on overflow instead of panicking or wrapping around.

Listing 12.20 The complete program. src/bin/dijkstra_with_lifetime.rs

use std::{
    cmp::Reverse,
    collections::{BinaryHeap, HashMap},
    hash::Hash,
};

#[derive(Debug)]
struct Edge<Node> {
    to: Node,
    weight: u64,
}

type AdjMap<Node> = HashMap<Node, Vec<Edge<Node>>>;

fn dijkstra_ssmd_shortest<'a, Node>(
    graph: &'a AdjMap<Node>,
    start: &'a Node,
) -> HashMap<&'a Node, u64>
where
    Node: Hash + Ord,
{
    let mut dist = HashMap::from([(start, 0u64)]);
    let mut heap = BinaryHeap::from([Reverse((0u64, start))]);

    while let Some(Reverse((cost, node))) = heap.pop() {
        if cost > dist[node] {
            continue; // stale entry
        }
        let Some(edges) = graph.get(node) else {
            continue;
        };

        for edge in edges {
            let Some(new_cost) = cost.checked_add(edge.weight) else {
                continue;
            };
            if dist
                .get(&edge.to)
                .is_none_or(|&d| new_cost < d)
            {
                dist.insert(&edge.to, new_cost);
                heap.push(Reverse((new_cost, &edge.to)));
            }
        }
    }
    dist
}

fn main() {
    let graph: AdjMap<String> = HashMap::from([
        (
            "A".into(),
            vec![
                Edge {
                    to: "B".into(),
                    weight: 4,
                },
                Edge {
                    to: "C".into(),
                    weight: 1,
                },
            ],
        ),
        (
            "B".into(),
            vec![Edge {
                to: "D".into(),
                weight: 1,
            }],
        ),
        (
            "C".into(),
            vec![
                Edge {
                    to: "B".into(),
                    weight: 2,
                },
                Edge {
                    to: "D".into(),
                    weight: 5,
                },
            ],
        ),
    ]);

    println!("Graph => {:#?}", graph);

    let start = "A".into();
    println!(
        "Shortest path {:#?}",
        dijkstra_ssmd_shortest(&graph, &start)
    ); // A:0, C:1, B:3, D:4
}

In main, let start = "A".into(); makes a String in its own variable, because the function needs a reference that lives as long as the graph borrow.

$ cargo run --bin dijkstra_with_lifetime
Graph => {
    ...
}
Shortest path {
    "A": 0,
    "B": 3,
    "D": 4,
    "C": 1,
}

The last version keeps the owned, cloning style of listing 12.18 and adds the two safety checks.

Listing 12.21 The complete program. src/bin/dijkstra_bruce_lee.rs

use std::{
    cmp::Reverse,
    collections::{BinaryHeap, HashMap},
    hash::Hash,
};

struct Edge<Node> {
    to: Node,
    weight: u64,
}

type AdjMap<Node> = HashMap<Node, Vec<Edge<Node>>>;

fn dijkstra_ssmd_shortest<Node>(graph: &AdjMap<Node>, start: Node) -> HashMap<Node, u64>
where
    Node: Clone + Hash + Ord,
{
    let mut dist = HashMap::from([(start.clone(), 0)]);
    let mut heap = BinaryHeap::from([Reverse((0u64, start))]);

    while let Some(Reverse((cost, node))) = heap.pop() {
        if cost > dist[&node] {
            continue; // stale entry
        }
        let Some(edges) = graph.get(&node) else {
            continue;
        }; // node with no outgoing edges

        for edge in edges {
            let Some(new_cost) = cost.checked_add(edge.weight) else {
                continue;
            }; // overflow
            if dist
                .get(&edge.to)
                .is_none_or(|&d| new_cost < d)
            {
                dist.insert(edge.to.clone(), new_cost);
                heap.push(Reverse((new_cost, edge.to.clone())));
            }
        }
    }
    dist
}

fn main() {
    let graph: AdjMap<&str> = HashMap::from([
        (
            "A",
            vec![Edge { to: "B", weight: 4 }, Edge { to: "C", weight: 1 }],
        ),
        ("B", vec![Edge { to: "D", weight: 1 }]),
        (
            "C",
            vec![Edge { to: "B", weight: 2 }, Edge { to: "D", weight: 5 }],
        ),
    ]); // "D" has no entry now, and it no longer panics

    println!("{:?}", dijkstra_ssmd_shortest(&graph, "A"));
}

$ cargo run --bin dijkstra_bruce_lee
{"B": 3, "C": 1, "D": 4, "A": 0}

Table 12.1 compares the five versions.

Table 12.1 The five Dijkstra implementations

12.10 Connecting every node at the lowest cost

The last problem uses an undirected, weighted graph. Think of the nodes as buildings and the weights as the cost of laying cable between two buildings. You want to connect every building, directly or indirectly, at the lowest total cost.

A set of edges that connects all the nodes without forming a cycle is a spanning tree. A spanning tree with the lowest total weight is a minimum spanning tree (MST). With n nodes, a spanning tree has exactly n − 1 edges. One edge fewer would leave a node disconnected, and one edge more would close a loop.

Kruskal’s algorithm builds an MST by taking edges from lightest to heaviest. It keeps an edge if the edge joins two groups of nodes that are not yet connected. It skips an edge whose two ends are already connected, because that edge would close a loop.

12.10.1 Union-find

Kruskal’s algorithm needs to answer one question fast: are these two nodes already connected? A union-find structure, also called a disjoint set, answers it.

Union-find keeps nodes in groups. Each group is a small tree stored in a parent array, where parent[i] is the node that i points to. The node at the top of a group points to itself and is called the group’s root. Two nodes are in the same group when they have the same root.

There are two operations:

• find(x) follows parent links from x up to the root.
• union(x, y) finds both roots. If the roots differ, it makes one root point to the other, which joins the two groups.

Listing 12.22 Union-find (lines 10 to 49). src/bin/kruskals_algorithm.rs

use std::cmp::Ordering::{Equal, Greater, Less};

struct DisjointSet {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl DisjointSet {
    fn new(n: usize) -> Self {
        Self {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    fn find(&mut self, elem: usize) -> usize {
        if self.parent[elem] != elem {
            self.parent[elem] = self.find(self.parent[elem]);
        }

        self.parent[elem]
    }

    fn union(&mut self, x: usize, y: usize) -> bool {
        let (x, y) = (self.find(x), self.find(y));

        if x == y {
            return false;
        }

        match self.rank[x].cmp(&self.rank[y]) {
            Less => self.parent[x] = y,
            Greater => self.parent[y] = x,
            Equal => {
                self.parent[x] = y;
                self.rank[y] += 1;
            }
        }

        true
    }
}

new makes every node its own group: parent is [0, 1, 2, ...], built with (0..n).collect().

find is recursive. On the way back from the root, it sets parent[elem] to the root directly. The next find on that node then takes one step instead of many. This trick is called path compression.

union returns false if both nodes already have the same root. Otherwise it joins the groups using rank, a rough measure of each group’s height. The shorter group goes under the taller one, so the trees stay flat. If both have the same rank, either can go under the other, and the new root’s rank grows by one. This is called union by rank.

With both tricks, find and union take nearly constant time in practice.

12.10.2 Kruskal’s algorithm

Listing 12.23 The edge type and Kruskal's algorithm (lines 3 to 65).

#[derive(Debug)]
struct Edge {
    u: usize,
    v: usize,
    w: u32,
}

fn kruskals(n: usize, mut edges: Vec<Edge>) -> Vec<Edge> {
    // Kruskal's algorithm is greedy: it takes the cheapest edges first.
    edges.sort_by_key(|e| e.w);

    let mut uf = DisjointSet::new(n);
    let mut mst = Vec::new();

    for edge in edges {
        if uf.union(edge.u, edge.v) {
            mst.push(edge);
        }
    }

    mst
}

An Edge joins nodes u and v, numbered from 0, with weight w. The graph is undirected, so the order of u and v does not matter.

edges.sort_by_key(|e| e.w) sorts the edges by weight. Then each edge is offered to union. If union returns true, the edge joined two groups, and it goes into the tree. The edge is moved into mst, not copied, because for edge in edges takes ownership of each one.

Sorting dominates the running time, so the algorithm runs in O(E log E).

Figure 12.8 follows the parent array through every edge of the program’s graph.

sort_by_key is a stable sort: edges with equal weights keep their input order. So 1-3 comes before 3-4, and 0-1 comes before 2-3.

Listing 12.24 The complete program. src/bin/kruskals_algorithm.rs

use std::cmp::Ordering::{Equal, Greater, Less};

#[derive(Debug)]
struct Edge {
    u: usize,
    v: usize,
    w: u32,
}

struct DisjointSet {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl DisjointSet {
    fn new(n: usize) -> Self {
        Self {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    fn find(&mut self, elem: usize) -> usize {
        if self.parent[elem] != elem {
            self.parent[elem] = self.find(self.parent[elem]);
        }

        self.parent[elem]
    }

    fn union(&mut self, x: usize, y: usize) -> bool {
        let (x, y) = (self.find(x), self.find(y));

        if x == y {
            return false;
        }

        match self.rank[x].cmp(&self.rank[y]) {
            Less => self.parent[x] = y,
            Greater => self.parent[y] = x,
            Equal => {
                self.parent[x] = y;
                self.rank[y] += 1;
            }
        }

        true
    }
}

fn kruskals(n: usize, mut edges: Vec<Edge>) -> Vec<Edge> {
    // Kruskal's algorithm is greedy: it takes the cheapest edges first.
    edges.sort_by_key(|e| e.w);

    let mut uf = DisjointSet::new(n);
    let mut mst = Vec::new();

    for edge in edges {
        if uf.union(edge.u, edge.v) {
            mst.push(edge);
        }
    }

    mst
}

fn main() {
    let edges = vec![
        Edge { u: 0, v: 1, w: 4 },
        Edge { u: 0, v: 2, w: 3 },
        Edge { u: 1, v: 2, w: 1 },
        Edge { u: 1, v: 3, w: 2 },
        Edge { u: 2, v: 3, w: 4 },
        Edge { u: 3, v: 4, w: 2 },
    ];

    let mst = kruskals(5, edges);
    let total: u32 = mst.iter().map(|e| e.w).sum();

    for e in &mst {
        println!("{} - {} ({})", e.u, e.v, e.w);
    }
    println!("total: {total}");
}

$ cargo run --bin kruskals_algorithm
1 - 2 (1)
1 - 3 (2)
3 - 4 (2)
0 - 2 (3)
total: 8

The tree has four edges for five nodes, as expected.

12.11 The complete files

The sections above showed these files in excerpts. Here each one is whole.

Listing 12.25 Breadth-first search, with its tests. src/problems/graph_bfs.rs

//! Breadth-first search.
//!
//! Two variants of the same algorithm:
//!
//! - `bfs_vec`: nodes are `usize` indices and the graph is `Vec<Vec<(usize, u32)>>`,
//!   so `visited` is a plain `Vec<bool>`. This is the version to write first.
//! - `bfs`: nodes are any `Copy + Eq + Hash` type and the graph is a `HashMap`
//!   from a node to a slice of `(neighbor, weight)` edges.

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

/// Adjacency list keyed by node: each node maps to its `(neighbor, weight)` edges.
pub type GraphAdjList<'a, Node> = HashMap<Node, &'a [(Node, u32)]>;

/// BFS over an index-based adjacency list. Returns nodes in visiting order.
pub fn bfs_vec(graph: &[Vec<(usize, u32)>], start_node: usize) -> Vec<usize> {
    let mut visited = vec![false; graph.len()];
    let mut queue = VecDeque::from([start_node]);
    let mut result = vec![];

    visited[start_node] = true;

    while let Some(current_node) = queue.pop_front() {
        result.push(current_node);
        for &(neighbor, _) in &graph[current_node] {
            if !visited[neighbor] {
                visited[neighbor] = true;
                queue.push_back(neighbor);
            }
        }
    }
    result
}

/// BFS over a `HashMap` adjacency list. Returns nodes in visiting order.
pub fn bfs<Node>(graph: &GraphAdjList<Node>, start_node: Node) -> Vec<Node>
where
    Node: Copy + Eq + Hash,
{
    let mut visited = HashSet::new();
    let mut queue = VecDeque::from([start_node]);
    let mut result = vec![];

    visited.insert(start_node);

    while let Some(current_node) = queue.pop_front() {
        result.push(current_node);
        // slice iter yields &(Node, u32); `&` destructures it
        for &(neighbor, _) in graph[&current_node] {
            if visited.insert(neighbor) {
                queue.push_back(neighbor);
            }
        }
    }
    result
}

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

    /// A -> B (1), A -> C (4), B -> C (2), B -> D (5), C -> D (1)
    fn sample_vec() -> Vec<Vec<(usize, u32)>> {
        vec![
            vec![(1, 1), (2, 4)],
            vec![(2, 2), (3, 5)],
            vec![(3, 1)],
            vec![],
        ]
    }

    fn sample_map() -> HashMap<&'static str, &'static [(&'static str, u32)]> {
        HashMap::from([
            ("A", &[("B", 1), ("C", 4)][..]),
            ("B", &[("C", 2), ("D", 5)][..]),
            ("C", &[("D", 1)][..]),
            ("D", &[][..]),
        ])
    }

    #[test]
    fn vec_variant_visits_level_by_level() {
        assert_eq!(bfs_vec(&sample_vec(), 0), vec![0, 1, 2, 3]);
    }

    #[test]
    fn vec_variant_skips_unreachable_nodes() {
        let graph = vec![vec![(1, 1)], vec![], vec![(0, 1)]];
        assert_eq!(bfs_vec(&graph, 0), vec![0, 1]);
    }

    #[test]
    fn vec_variant_handles_cycles() {
        let graph = vec![vec![(1, 1)], vec![(0, 1)]];
        assert_eq!(bfs_vec(&graph, 0), vec![0, 1]);
    }

    #[test]
    fn map_variant_visits_level_by_level() {
        assert_eq!(bfs(&sample_map(), "A"), vec!["A", "B", "C", "D"]);
    }

    #[test]
    fn both_variants_agree() {
        let names = ["A", "B", "C", "D"];
        let from_vec: Vec<&str> = bfs_vec(&sample_vec(), 0)
            .into_iter()
            .map(|index| names[index])
            .collect();
        assert_eq!(from_vec, bfs(&sample_map(), "A"));
    }
}

Listing 12.26 Depth-first search, with its tests. src/problems/graph_dfs.rs

//! Iterative depth-first search with an explicit stack.
//!
//! Two variants of the same algorithm:
//!
//! - `dfs_vec`: nodes are `usize` indices and the graph is `Vec<Vec<(usize, u32)>>`.
//! - `dfs`: nodes are any `Copy + Eq + Hash` type and the graph is a `HashMap`.
//!
//! A node is marked visited when it is popped, not when it is pushed, so it may
//! sit on the stack more than once. Neighbors are pushed in order, which means the
//! last neighbor is explored first.

use std::{collections::HashSet, hash::Hash};

use crate::problems::graph_bfs::GraphAdjList;

/// DFS over an index-based adjacency list. Returns nodes in visiting order.
pub fn dfs_vec(graph: &[Vec<(usize, u32)>], start_node: usize) -> Vec<usize> {
    let mut visited = vec![false; graph.len()];
    let mut stack = vec![start_node];
    let mut result = vec![];

    while let Some(current_node) = stack.pop() {
        if visited[current_node] {
            continue;
        }
        visited[current_node] = true;
        result.push(current_node);
        for &(neighbor, _) in &graph[current_node] {
            stack.push(neighbor);
        }
    }
    result
}

/// DFS over a `HashMap` adjacency list. Returns nodes in visiting order.
pub fn dfs<Node>(graph: &GraphAdjList<Node>, start_node: Node) -> Vec<Node>
where
    Node: Copy + Eq + Hash,
{
    let mut visited = HashSet::new();
    let mut stack = vec![start_node];
    let mut result = vec![];

    while let Some(current_node) = stack.pop() {
        if !visited.insert(current_node) {
            continue;
        }
        result.push(current_node);
        for &(neighbor, _) in graph[&current_node] {
            stack.push(neighbor);
        }
    }
    result
}

#[cfg(test)]
mod tests {
    use std::collections::HashMap;

    use super::*;

    /// A -> B (1), A -> C (4), B -> C (2), B -> D (5), C -> D (1)
    fn sample_vec() -> Vec<Vec<(usize, u32)>> {
        vec![
            vec![(1, 1), (2, 4)],
            vec![(2, 2), (3, 5)],
            vec![(3, 1)],
            vec![],
        ]
    }

    fn sample_map() -> HashMap<&'static str, &'static [(&'static str, u32)]> {
        HashMap::from([
            ("A", &[("B", 1), ("C", 4)][..]),
            ("B", &[("C", 2), ("D", 5)][..]),
            ("C", &[("D", 1)][..]),
            ("D", &[][..]),
        ])
    }

    #[test]
    fn vec_variant_explores_the_last_neighbor_first() {
        // Pop 0, push 1 and 2; pop 2, push 3; pop 3; pop 1.
        assert_eq!(dfs_vec(&sample_vec(), 0), vec![0, 2, 3, 1]);
    }

    #[test]
    fn vec_variant_handles_cycles() {
        let graph = vec![vec![(1, 1)], vec![(2, 1)], vec![(0, 1)]];
        assert_eq!(dfs_vec(&graph, 0), vec![0, 1, 2]);
    }

    #[test]
    fn map_variant_explores_the_last_neighbor_first() {
        assert_eq!(dfs(&sample_map(), "A"), vec!["A", "C", "D", "B"]);
    }

    #[test]
    fn both_variants_agree() {
        let names = ["A", "B", "C", "D"];
        let from_vec: Vec<&str> = dfs_vec(&sample_vec(), 0)
            .into_iter()
            .map(|index| names[index])
            .collect();
        assert_eq!(from_vec, dfs(&sample_map(), "A"));
    }
}

Listing 12.27 Dijkstra's algorithm, with its tests. src/problems/graph_dijkstra.rs

//! Dijkstra's shortest paths with a binary min-heap.
//!
//! Two variants of the same algorithm:
//!
//! - `dijkstra_vec`: nodes are `usize` indices and distances are a
//!   `Vec<Option<u32>>`, where `None` means unreachable.
//! - `dijkstra`: nodes are any `Copy + Eq + Hash + Ord` type and distances are a
//!   `HashMap` containing only the reachable nodes.
//!
//! Edge weights must be non-negative, which `u32` guarantees. `BinaryHeap` is a
//! max-heap, so entries are wrapped in `Reverse` to pop the smallest cost first.
//! A node can be in the heap several times; an entry whose cost is larger than the
//! recorded distance is stale and skipped.

use std::{
    cmp::Reverse,
    collections::{BinaryHeap, HashMap},
    hash::Hash,
};

use crate::problems::graph_bfs::GraphAdjList;

/// Shortest distances from `start_node` over an index-based adjacency list.
pub fn dijkstra_vec(graph: &[Vec<(usize, u32)>], start_node: usize) -> Vec<Option<u32>> {
    let mut distances = vec![None; graph.len()];
    let mut min_heap = BinaryHeap::from([Reverse((0, start_node))]);

    distances[start_node] = Some(0);

    while let Some(Reverse((current_cost, current_node))) = min_heap.pop() {
        // stale heap entry, a shorter path was already recorded
        if distances[current_node].is_some_and(|best| current_cost > best) {
            continue;
        }
        for &(neighbor, weight) in &graph[current_node] {
            let new_distance = current_cost + weight;
            if distances[neighbor].is_none_or(|best| new_distance < best) {
                distances[neighbor] = Some(new_distance);
                min_heap.push(Reverse((new_distance, neighbor)));
            }
        }
    }
    distances
}

/// Shortest distances from `start_node` over a `HashMap` adjacency list.
pub fn dijkstra<Node>(graph: &GraphAdjList<Node>, start_node: Node) -> HashMap<Node, u32>
where
    Node: Copy + Eq + Hash + Ord,
{
    let mut distances = HashMap::from([(start_node, 0)]);
    let mut min_heap = BinaryHeap::from([Reverse((0, start_node))]);

    while let Some(Reverse((current_cost, current_node))) = min_heap.pop() {
        // stale heap entry, a shorter path was already recorded
        if current_cost > distances[&current_node] {
            continue;
        }
        for &(neighbor, weight) in graph[&current_node] {
            let new_distance = current_cost + weight;

            if new_distance
                < *distances
                    .get(&neighbor)
                    .unwrap_or(&u32::MAX)
            {
                distances.insert(neighbor, new_distance);
                min_heap.push(Reverse((new_distance, neighbor)));
            }
        }
    }
    distances
}

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

    /// A -> B (1), A -> C (4), B -> C (2), B -> D (5), C -> D (1)
    fn sample_vec() -> Vec<Vec<(usize, u32)>> {
        vec![
            vec![(1, 1), (2, 4)],
            vec![(2, 2), (3, 5)],
            vec![(3, 1)],
            vec![],
        ]
    }

    fn sample_map() -> HashMap<&'static str, &'static [(&'static str, u32)]> {
        HashMap::from([
            ("A", &[("B", 1), ("C", 4)][..]),
            ("B", &[("C", 2), ("D", 5)][..]),
            ("C", &[("D", 1)][..]),
            ("D", &[][..]),
        ])
    }

    #[test]
    fn vec_variant_finds_shorter_multi_hop_paths() {
        // A -> C directly costs 4, A -> B -> C costs 3; D is reached via C for 4.
        assert_eq!(
            dijkstra_vec(&sample_vec(), 0),
            vec![Some(0), Some(1), Some(3), Some(4)]
        );
    }

    #[test]
    fn vec_variant_marks_unreachable_nodes() {
        let graph = vec![vec![(1, 7)], vec![], vec![(0, 1)]];
        assert_eq!(dijkstra_vec(&graph, 0), vec![Some(0), Some(7), None]);
    }

    #[test]
    fn map_variant_finds_shorter_multi_hop_paths() {
        let distances = dijkstra(&sample_map(), "A");
        assert_eq!(
            distances,
            HashMap::from([("A", 0), ("B", 1), ("C", 3), ("D", 4)])
        );
    }

    #[test]
    fn map_variant_omits_unreachable_nodes() {
        let graph: HashMap<u8, &[(u8, u32)]> =
            HashMap::from([(0, &[(1, 2)][..]), (1, &[][..]), (2, &[(0, 1)][..])]);
        assert_eq!(dijkstra(&graph, 0), HashMap::from([(0, 0), (1, 2)]));
    }
}

Chapter 13 builds an LRU cache, which combines a hash map with a linked list. It brings back the ownership questions of chapters 8 and 9.

Exercises

1. Change bfs_vec in listing 12.1 to also return, for each node, the number of edges on the shortest path from the start.
2. Extend dijkstra_vec to record each node’s predecessor on its shortest path. Then write a function that rebuilds the path from the start to a given node.
3. Rewrite count_islands with a Vec<bool> for visited, and with a DFS stack instead of a BFS queue. Check that the tests still pass.
4. Change topo_sort in listing 12.15 to return Option<Vec<String>>, and add a test with a cycle.
5. Rewrite find in listing 12.22 with a loop instead of recursion, keeping path compression.