Adjacency List Representation in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare an adjacency list as a vector of vectors.

DSA Rust

let mut graph: Vec<Vec<usize>> = [1];

Drag options to blanks, or click blank then click option'

Avec![vec![]; 5]

Bvec![0; 5]

CHashMap::new()

DVec::new()

Attempts:

3 left

💡 Hint

Common Mistakes

Using Vec::new() creates an empty vector with no inner vectors.

Using vec![0; 5] creates a vector of zeros, not vectors.

We use vec![vec![]; 5] to create a vector with 5 empty vectors, representing adjacency lists for 5 nodes.

2fill in blank

medium

Complete the code to add an edge from node 1 to node 3 in the adjacency list.

DSA Rust

graph[1].[1](3);

Drag options to blanks, or click blank then click option'

Apush

Binsert

Cappend

Dextend

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert without an index causes errors.

Using append or extend expects another vector, not a single element.

We use push to add a new neighbor to the adjacency list vector for node 1.

3fill in blank

hard

Fix the error in this code that tries to print neighbors of node 2.

DSA Rust

for &neighbor in &graph[[1]] {
    println!("{}", neighbor);
}

Drag options to blanks, or click blank then click option'

A1

B3

C2

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong node index causes printing neighbors of a different node.

Using an index out of bounds causes runtime panic.

We want to print neighbors of node 2, so the index must be 2.

4fill in blank

hard

Fill both blanks to create an adjacency list for 4 nodes and add an edge from node 0 to node 2.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Avec![]

Bpush

Cvec![0]

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using vec![0] creates vectors with zero inside, not empty.

Using insert without index causes errors.

We create 4 empty vectors for nodes, then push 2 to node 0's adjacency list.

5fill in blank

hard

Fill all three blanks to initialize a graph with 3 nodes, add edges 0->1 and 1->2, then print neighbors of node 1.

DSA Rust

let mut graph = vec![[1]; 3];
graph[0].[2](1);
graph[1].[3](2);
for &neighbor in &graph[1] {
    println!("{}", neighbor);
}

Drag options to blanks, or click blank then click option'

Avec![]

Bpush

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert without index causes errors.

Initializing with vec![0] creates vectors with zero, not empty.

We create empty adjacency lists, then push neighbors 1 and 2 to nodes 0 and 1 respectively, then print neighbors of node 1.

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