Adjacency List Representation in DSA Rust

Mental Model

We store each node's neighbors in a list so we can quickly see who it connects to.

Analogy: Imagine a group of friends where each person keeps a list of their close friends. To find who someone knows, you just look at their list.

0 -> [1, 2]
1 -> [2]
2 -> [0, 3]
3 -> []

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: 0->1, 0->2, 1->2, 2->0, 2->3

Goal: Build the adjacency list to show neighbors for each node

Step 1: Add edge from 0 to 1

0 -> [1]
1 -> []
2 -> []
3 -> []

Why: Start by listing node 0's neighbor 1

Step 2: Add edge from 0 to 2

0 -> [1, 2]
1 -> []
2 -> []
3 -> []

Why: Add another neighbor 2 to node 0's list

Step 3: Add edge from 1 to 2

0 -> [1, 2]
1 -> [2]
2 -> []
3 -> []

Why: Node 1 connects to node 2

Step 4: Add edge from 2 to 0

0 -> [1, 2]
1 -> [2]
2 -> [0]
3 -> []

Why: Node 2 connects back to node 0

Step 5: Add edge from 2 to 3

0 -> [1, 2]
1 -> [2]
2 -> [0, 3]
3 -> []

Why: Node 2 also connects to node 3

Result:

0 -> [1, 2]
1 -> [2]
2 -> [0, 3]
3 -> []

Annotated Code

DSA Rust

use std::collections::HashMap;

struct Graph {
    adjacency_list: HashMap<usize, Vec<usize>>,
}

impl Graph {
    fn new() -> Self {
        Graph {
            adjacency_list: HashMap::new(),
        }
    }

    fn add_edge(&mut self, from: usize, to: usize) {
        self.adjacency_list.entry(from).or_insert(Vec::new()).push(to);
        // Ensure all nodes appear in the adjacency list even if no outgoing edges
        self.adjacency_list.entry(to).or_insert(Vec::new());
    }

    fn print(&self) {
        let mut keys: Vec<_> = self.adjacency_list.keys().cloned().collect();
        keys.sort();
        for node in keys {
            let neighbors = &self.adjacency_list[&node];
            let neighbors_str = neighbors.iter().map(|n| n.to_string()).collect::<Vec<_>>().join(", ");
            println!("{} -> [{}]", node, neighbors_str);
        }
    }
}

fn main() {
    let mut graph = Graph::new();
    graph.add_edge(0, 1);
    graph.add_edge(0, 2);
    graph.add_edge(1, 2);
    graph.add_edge(2, 0);
    graph.add_edge(2, 3);
    graph.print();
}

self.adjacency_list.entry(from).or_insert(Vec::new()).push(to);

Add 'to' node to 'from' node's neighbors list

self.adjacency_list.entry(to).or_insert(Vec::new());

Ensure 'to' node exists in adjacency list even if no outgoing edges

let neighbors = &self.adjacency_list[&node];

Access neighbors list for current node to print

Output

0 -> [1, 2]

1 -> [2]

2 -> [0, 3]

3 -> []

Complexity Analysis

Time: O(E) because we add each edge once to the adjacency list

Space: O(V + E) because we store each node and all its edges

vs Alternative: Compared to adjacency matrix which uses O(V^2) space, adjacency list is more space efficient for sparse graphs

Edge Cases

Graph with no edges

Nodes appear with empty neighbor lists

DSA Rust

self.adjacency_list.entry(to).or_insert(Vec::new());

Graph with single node and no edges

Node appears with empty neighbor list

DSA Rust

self.adjacency_list.entry(to).or_insert(Vec::new());

Adding duplicate edges

Duplicates appear in neighbor list as is

DSA Rust

self.adjacency_list.entry(from).or_insert(Vec::new()).push(to);

When to Use This Pattern

When you need to represent a graph and quickly find neighbors of a node, use adjacency list because it stores only existing edges efficiently.

Common Mistakes

Mistake: Not adding nodes with no outgoing edges to the adjacency list
Fix: Add an entry for 'to' node with empty list to ensure all nodes appear

Mistake: Using a fixed-size array for adjacency list which wastes space for sparse graphs
Fix: Use a dynamic map or list structure to store neighbors only when edges exist

Summary

Stores each node's neighbors in a list for efficient graph representation.

Use when you want to save space and quickly access neighbors in a graph.

The key is to keep a list of neighbors for each node instead of a big matrix.

Practice

1. What does an adjacency list represent in graph data structures?

easy

A. A list of all nodes without connections

B. A matrix showing distances between nodes

C. A list where each node stores its connected neighbors

D. A queue of nodes to visit next

Solution

1. Step 1: Understand graph representation

   An adjacency list stores each node with a list of its neighbors, showing direct connections.

2. Step 2: Compare options

   Only A list where each node stores its connected neighbors describes this correctly; others describe different structures or concepts.

3. Final Answer:

   A list where each node stores its connected neighbors -> Option C

4. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list = node with its neighbors [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking adjacency list stores distances
• Mixing up with traversal queues

2. Which Rust data structure is best suited to represent an adjacency list for a graph with nodes labeled 0 to n-1?

easy

A. Vec

B. HashMap

C. Vec<usize>

D. HashSet<usize>

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list for nodes 0 to n-1 is a vector where each index holds a vector of neighbors.

2. Step 2: Match Rust types

   Vec matches this: outer Vec for nodes, inner Vec for neighbors. Others don't store neighbors per node properly.

3. Final Answer:

   Vec -> Option A

4. Quick Check:

   Vec of Vecs = adjacency list [OK]

Hint: Use Vec for adjacency list in Rust [OK]

Common Mistakes:

• Using HashMap with single usize value instead of list
• Using Vec<usize> which holds only one neighbor list
• Using HashSet which doesn't map nodes to neighbors

3. Given the following Rust code, what is the printed adjacency list?

let mut graph: Vec = vec![vec![], vec![], vec![]];
graph[0].push(1);
graph[1].push(2);
graph[2].push(0);
println!("{:?}", graph);

medium

A. [[0], [1], [2]]

B. [[1], [2], [0]]

C. [[], [], []]

D. [[2], [0], [1]]

Solution

1. Step 1: Trace graph initialization

   graph starts as three empty vectors: [[], [], []]

2. Step 2: Apply push operations

   graph[0].push(1) -> [[1], [], []] graph[1].push(2) -> [[1], [2], []] graph[2].push(0) -> [[1], [2], [0]]

3. Final Answer:

   [[1], [2], [0]] -> Option B

4. Quick Check:

   Push neighbors correctly = [[1], [2], [0]] [OK]

Hint: Follow push calls step-by-step [OK]

Common Mistakes:

• Mixing indices when pushing neighbors
• Assuming graph is empty after pushes
• Confusing order of neighbors

4. Identify the error in this Rust code snippet for creating an adjacency list:

let mut graph: Vec = Vec::new();
graph[0].push(1);

medium

A. Vec::new() cannot be mutable

B. usize type is incorrect for adjacency list

C. push method does not exist for Vec

D. graph is empty, so graph[0] access causes panic

Solution

1. Step 1: Analyze graph initialization

   graph is empty Vec with no elements, so graph[0] does not exist.

2. Step 2: Understand indexing error

   Accessing graph[0] causes runtime panic because index 0 is out of bounds.

3. Final Answer:

   graph is empty, so graph[0] access causes panic -> Option D

4. Quick Check:

   Empty Vec indexing = panic [OK]

Hint: Initialize Vec with size before indexing [OK]

Common Mistakes:

• Assuming Vec::new() has elements
• Confusing mutability with initialization
• Thinking push is invalid method

5. You want to represent a directed graph with 4 nodes using an adjacency list in Rust. Which code correctly initializes the graph and adds edges from node 0 to 1 and 2, and from node 2 to 3?

hard

A. let mut graph = vec![vec![], vec![], vec![], vec![]];
graph[0].push(1);
graph[0].push(2);
graph[2].push(3);

B. let mut graph = Vec::new();
graph[0].push(1);
graph[0].push(2);
graph[2].push(3);

C. let mut graph = vec![0; 4];
graph[0] = 1;
graph[0] = 2;
graph[2] = 3;

D. let mut graph = vec![vec![0]; 4];
graph[0].push(1);
graph[0].push(2);
graph[2].push(3);

Solution

1. Step 1: Check graph initialization

   let mut graph = vec![vec![], vec![], vec![], vec![]]; graph[0].push(1); graph[0].push(2); graph[2].push(3); initializes a Vec of Vecs with 4 empty vectors, ready to hold neighbors.

2. Step 2: Verify edge additions

   graph[0].push(1) and graph[0].push(2) add edges from node 0 to 1 and 2; graph[2].push(3) adds edge from 2 to 3.

3. Step 3: Identify errors in other options

   let mut graph = Vec::new(); graph[0].push(1); graph[0].push(2); graph[2].push(3);: graph is empty Vec, indexing causes panic. let mut graph = vec![0; 4]; graph[0] = 1; graph[0] = 2; graph[2] = 3;: graph is Vec<usize>, not Vec; push invalid. let mut graph = vec![vec![0]; 4]; graph[0].push(1); graph[0].push(2); graph[2].push(3);: graph initialized with vec![vec![0]; 4] means each node starts with neighbor 0, incorrect.

4. Final Answer:

   let mut graph = vec![vec![], vec![], vec![], vec![]]; graph[0].push(1); graph[0].push(2); graph[2].push(3); -> Option A

5. Quick Check:

   Vec of empty Vecs + push edges = correct [OK]

Hint: Initialize Vec with empty Vecs before pushing [OK]

Common Mistakes:

• Using empty Vec without size causes panic
• Initializing with repeated vec![0] adds wrong neighbors
• Using Vec<usize> instead of Vec