Adjacency List Representation in DSA Rust - Build from Scratch

Adjacency List Representation

📖 Scenario: You are working on a simple social network app. Each user can have friends. You want to store the friendship connections efficiently.

🎯 Goal: Build an adjacency list representation of a graph using a Rust HashMap where each user is a key and the value is a list of their friends.

📋 What You'll Learn

Create a HashMap called friends with exact user keys and friend lists

Add a variable user to select a specific user

Use the get method on friends with user to get the friend list

Print the friend list for the selected user

💡 Why This Matters

🌍 Real World

Social networks, recommendation systems, and many graph-based problems use adjacency lists to store connections efficiently.

💼 Career

Understanding adjacency lists is fundamental for software engineers working with graph algorithms, network analysis, and data structures.

1

Create the adjacency list

Create a HashMap called friends with these exact entries: "Alice" maps to vec!["Bob", "Charlie"], "Bob" maps to vec!["Alice"], and "Charlie" maps to vec!["Alice"].

DSA Rust

use std::collections::HashMap;

// Create the friends HashMap with exact entries
// Your code here

Hint

Use HashMap::new() to create the map. Use insert to add each user and their friends.

2

Select a user

Add a variable called user and set it to the string "Alice".

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut friends: HashMap> = HashMap::new();
    friends.insert("Alice", vec!["Bob", "Charlie"]);
    friends.insert("Bob", vec!["Alice"]);
    friends.insert("Charlie", vec!["Alice"]);

    // Add a variable user and set it to "Alice"
    // Your code here
}

Hint

Use let user = "Alice"; to create the variable.

3

Get the friend list for the user

Use the get method on friends with user to get the friend list. Store the result in a variable called user_friends. Use unwrap() to get the vector from the Option.

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut friends: HashMap> = HashMap::new();
    friends.insert("Alice", vec!["Bob", "Charlie"]);
    friends.insert("Bob", vec!["Alice"]);
    friends.insert("Charlie", vec!["Alice"]);

    let user = "Alice";

    // Get the friend list for user and store in user_friends
    // Your code here
}

Hint

Use friends.get(user).unwrap() to get the vector of friends.

4

Print the friend list

Print the user_friends variable using println! with the format string "{}'s friends: {:?}" and arguments user and user_friends.

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut friends: HashMap> = HashMap::new();
    friends.insert("Alice", vec!["Bob", "Charlie"]);
    friends.insert("Bob", vec!["Alice"]);
    friends.insert("Charlie", vec!["Alice"]);

    let user = "Alice";

    let user_friends = friends.get(user).unwrap();

    // Print the friend list for user
    // Your code here
}

Hint

Use println!("{}'s friends: {:?}", user, user_friends); to print the list.

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