Step 1 of 7

Representing graphs: adjacency lists

A graph is a set of nodes (also called vertices) connected by edges. Edges can be directed (one-way: "A depends on B", "A follows B", a link from page A to page B) or undirected (two-way: a friendship, a road, a network cable), and weighted (a distance, a cost, a latency) or not.

Graphs are everywhere at work even when nobody calls them that: build dependencies, microservice call chains, org charts, permission inheritance, routes between warehouses, the states of an order.

Storing a graph

Number the nodes 0..n and keep, for every node, the list of its neighbors: an adjacency list, Vec<Vec<usize>>. adj[u] lists every v with an edge u -> v. Memory is O(V + E) (nodes plus edges), and walking a node's neighbors is as fast as it gets. It's the default choice.

Input usually arrives as an edge list, pairs of nodes. Turning it into adjacency lists:

fn main() {
    // 5 stations, undirected tracks between them
    let n = 5;
    let tracks = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)];
    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
    for &(a, b) in &tracks {
        adj[a].push(b);
        adj[b].push(a); // undirected: the edge goes both ways
    }
    for (station, neighbors) in adj.iter().enumerate() {
        println!("{station}: {neighbors:?} (degree {})", neighbors.len());
    }
}

0: [1, 2] (degree 2)
1: [0, 3] (degree 2)
2: [0, 3] (degree 2)
3: [1, 2, 4] (degree 3)
4: [3] (degree 1)

The degree of a node is its number of edges. In a directed graph you count out-degree (edges leaving) and in-degree (edges arriving) separately.

The alternatives:

• An adjacency matrix Vec<Vec<bool>> of size n by n answers "is there an edge u-v?" in O(1), but uses O(V²) memory: 100,000 nodes would need 10 billion cells. Only for small, dense graphs.
• Named nodes: give each name an index with a HashMap<String, usize> (and a Vec<String> to go back), then use adjacency lists of indices. For small graphs, a BTreeMap<String, BTreeSet<String>> directly is fine and prints in a stable order.

Why indices and not references?

In other languages a node might hold pointers to its neighbors. In Rust, nodes holding &Node references to each other fight the borrow checker (graphs have cycles, and who would own whom?). Rc<RefCell<Node>> works but is clumsy. Storing nodes in a Vec and referring to them by index is the idiomatic Rust approach, used by real crates like petgraph.

Common mistakes

• Forgetting the reverse edge in an undirected graph, so you can travel A to B but not back.
• 1-based ids from the input. If nodes are numbered 1 to n, either subtract 1 or make the Vec n + 1 long; otherwise adj[n] panics with index out of bounds.
• Duplicate edges and self-loops ((2, 2)). Decide what they mean; many algorithms assume there are none.

Your task

Write fn build_graph(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> for an undirected graph with nodes 0..n. Clean the data while you're at it: each neighbor list must be sorted ascending with no duplicates (the same edge may appear twice, in either direction). A self-loop (a, a) makes a appear once in its own list.

Challenge 2

A social app wants to find the hub of a group of n people (numbered 0..n): the person whom everyone else follows, but who follows nobody. Each pair (a, b) in follows means a follows b (no pair appears twice, nobody follows themselves). Write fn find_hub(n: usize, follows: &[(usize, usize)]) -> Option<usize>. In a group of one, that person is the hub.

You don't need adjacency lists for this: count each person's in-degree and out-degree in two Vec<usize>s. The hub has in-degree n - 1 and out-degree 0. The tests include 100,000 people.

Challenge 3

The friends page needs each person's friend list. Standard input has one friendship per line, two names separated by a space (ana ben means they're friends with each other). Print every person in alphabetical order with their friends, alphabetically, separated by , :

ana: ben, cy
ben: ana
cy: ana

Use a BTreeMap<String, BTreeSet<String>> as the adjacency list: the BTree types keep both levels sorted, and a set ignores repeated friendships. Skip blank lines.

Next: Breadth-first search with VecDeque