Adjacency List vs Matrix When to Choose Which in DSA Rust - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA Rust

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

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

AVec::new()

Bvec![0; 5]

CHashMap::new()

Dvec![vec![]; 5]

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 initialize an adjacency matrix for 4 nodes with all zeros.

DSA Rust

let matrix: Vec<Vec<u8>> = vec![vec![[1]; 4]; 4];

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

A1

BNone

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 would indicate edges exist.

Using None or -1 is not valid for u8 type.

We fill the matrix with zeros to indicate no edges initially.

3fill in blank

hard

Fix the error in adding an edge from node 2 to node 3 in an adjacency list.

DSA Rust

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

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

Apush

Binsert

Cappend

Dadd

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert requires an index and is not the best for adding at the end.

append is for vectors, not single elements.

add is not a method on vectors.

We use push to add an element to the vector representing adjacency list.

4fill in blank

hard

Fill both blanks to check if there is an edge from node 1 to node 2 in an adjacency matrix.

DSA Rust

if matrix[[1]][[2]] == 1 {
    println!("Edge exists");
}

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

A1

B0

C2

D3

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 3 as indices would check wrong nodes.

Checking for 0 means no edge.

We check matrix[1][2] to see if an edge exists from node 1 to node 2.

5fill in blank

hard

Fill all three blanks to create an adjacency list for 3 nodes and add an edge from node 0 to node 2.

DSA Rust

let mut graph: Vec<Vec<usize>> = vec![vec![]; [1]];
graph[[2]].[3](2);

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

A3

B0

Cpush

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong number of nodes in initialization.

Using wrong source node index.

Using incorrect method to add edge.

We create a graph with 3 nodes, then add an edge from node 0 to node 2 using push.

Practice

1. Which data structure is generally better for representing a graph with very few edges compared to the number of vertices?

easy

A. Adjacency List

B. Adjacency Matrix

C. Edge List

D. Incidence Matrix

Solution

1. Step 1: Understand graph density

   A graph with very few edges compared to vertices is called sparse.

2. Step 2: Choose data structure for sparse graphs

   Adjacency List stores only existing edges, saving space for sparse graphs.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graphs use adjacency lists for space efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes space
• Confusing edge list with adjacency matrix
• Assuming adjacency matrix is always better

2. Which of the following is the correct Rust syntax to declare an adjacency matrix using a 2D vector for a graph with 3 vertices initialized to zero?

easy

A. let matrix = vec![vec![0; 2]; 3];

B. let matrix = [[0; 3]; 3];

C. let matrix = vec![0; 3];

D. let matrix = vec![vec![0; 3]; 3];

Solution

1. Step 1: Understand adjacency matrix structure

   It is a 2D structure with size n x n, here 3 x 3.

2. Step 2: Check Rust syntax for 2D vector initialization

   vec![vec![0; 3]; 3] creates a 3x3 matrix filled with zeros.

3. Final Answer:

   let matrix = vec![vec![0; 3]; 3]; -> Option D

4. Quick Check:

   3x3 zero matrix = vec![vec![0; 3]; 3] [OK]

Hint: Use vec![vec![value; cols]; rows] for 2D vectors [OK]

Common Mistakes:

• Using single vector for 2D matrix
• Wrong inner vector size
• Using fixed-size array without mutability

3. Given the following Rust code for an adjacency list, what will be printed?

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

medium

A. [1, 2]

B. [0, 1]

C. [0]

D. [2, 1]

Solution

1. Step 1: Understand adjacency list structure

   graph[0] contains neighbors of vertex 0, which are 1 and 2.

2. Step 2: Check printed output

   Printing graph[0] shows the vector [1, 2].

3. Final Answer:

   [1, 2] -> Option A

4. Quick Check:

   graph[0] = [1, 2] [OK]

Hint: Access adjacency list by index to get neighbors [OK]

Common Mistakes:

• Confusing indices and values
• Expecting sorted output
• Mixing adjacency matrix with list

4. Identify the error in this Rust code snippet for creating an adjacency matrix and fix it:

let mut matrix = vec![vec![0; 3]; 3];
matrix[0][1] = 1;
matrix[1][3] = 1;

medium

A. Use a 4x4 matrix instead of 3x3;

B. Index 3 is out of bounds; change to matrix[1][2] = 1;

C. Change vec![0; 3] to vec![0; 4];

D. No error; code runs fine

Solution

1. Step 1: Check matrix size and indices

   Matrix is 3x3, valid indices are 0,1,2 for both rows and columns.

2. Step 2: Identify invalid index usage

   matrix[1][3] accesses column 3 which is out of bounds.

3. Step 3: Fix the index

   Change matrix[1][3] to matrix[1][2] to stay within bounds.

4. Final Answer:

   Index 3 is out of bounds; change to matrix[1][2] = 1; -> Option B

5. Quick Check:

   3x3 matrix max index = 2 [OK]

Hint: Indices start at 0; max index = size-1 [OK]

Common Mistakes:

• Using index equal to size (out of bounds)
• Assuming 1-based indexing
• Ignoring Rust's strict bounds checking

5. You need to represent a dense graph with 1000 vertices where you frequently check if an edge exists between any two vertices. Which representation is best and why?

hard

A. Edge List, because it is fastest for dense graphs

B. Adjacency List, because it uses less memory for dense graphs

C. Adjacency Matrix, because it allows O(1) edge existence checks

D. Adjacency Matrix, because it uses less memory for sparse graphs

Solution

1. Step 1: Analyze graph density and operations

   Dense graph means many edges, close to maximum possible.

2. Step 2: Choose data structure for fast edge checks

   Adjacency matrix allows O(1) time to check if edge exists by direct index access.

3. Step 3: Consider memory tradeoff

   Though adjacency matrix uses more memory, for dense graphs this is acceptable and efficient.

4. Final Answer:

   Adjacency Matrix, because it allows O(1) edge existence checks -> Option C

5. Quick Check:

   Dense graph + fast edge check = Adjacency Matrix [OK]

Hint: Dense graphs + frequent edge checks = adjacency matrix [OK]

Common Mistakes:

• Choosing adjacency list for dense graphs wastes time
• Confusing edge list speed with adjacency matrix
• Incorrectly thinking adjacency matrix saves memory for sparse graphs