Adjacency List vs Matrix When to Choose Which in DSA Rust - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to prefer adjacency list over adjacency matrix?

Which scenario is best suited for using an adjacency list instead of an adjacency matrix?

A When the graph is sparse with relatively few edges compared to vertices

B When the graph is dense with many edges close to the maximum possible

C When you need to quickly check if an edge exists between two vertices

D When the graph has a fixed small number of vertices and many edges

💡 Hint

Think about memory usage and efficiency when edges are few.

An adjacency list uses less memory and is faster for sparse graphs because it stores only existing edges. Adjacency matrix uses fixed space for all possible edges, which is wasteful for sparse graphs.

❓ Predict Output

intermediate

Output of adjacency matrix for a small graph

What is the printed adjacency matrix after adding edges (0->1), (1->2), and (2->0) in a graph with 3 vertices?

DSA Rust

let mut matrix = vec![vec![0; 3]; 3];
matrix[0][1] = 1;
matrix[1][2] = 1;
matrix[2][0] = 1;
for row in &matrix {
    println!("{:?}", row);
}

A [[1, 0, 0], [0, 1, 0], [0, 0, 1]]

B [[0, 1, 0], [0, 0, 1], [1, 0, 0]]

C [[0, 0, 1], [1, 0, 0], [0, 1, 0]]

D [[0, 1, 1], [1, 0, 1], [1, 1, 0]]

💡 Hint

Check which indices are set to 1 for edges.

The matrix rows represent source vertices and columns represent destination vertices. Setting matrix[0][1] = 1 means edge from 0 to 1.

❓ Predict Output

advanced

Output of adjacency list after adding edges

What is the printed adjacency list after adding edges (0->2), (0->1), and (1->2) in a graph with 3 vertices?

DSA Rust

let mut adj_list: Vec<Vec<usize>> = vec![vec![], vec![], vec![]];
adj_list[0].push(2);
adj_list[0].push(1);
adj_list[1].push(2);
for (i, neighbors) in adj_list.iter().enumerate() {
    print!("{} -> ", i);
    for &n in neighbors {
        print!("{} -> ", n);
    }
    println!("null");
}

A

0 -> 2 -> null
1 -> 2 -> 1 -> null
2 -> null

B

0 -> 1 -> 2 -> null
1 -> 2 -> null
2 -> null

C

0 -> 2 -> 1 -> null
1 -> 2 -> null
2 -> null

D

0 -> null
1 -> 2 -> null
2 -> 0 -> 1 -> null

💡 Hint

Remember the order edges were added to each list.

Edges are stored in the order they are added. For vertex 0, edges to 2 and then 1 are added, so neighbors are [2,1].

🧠 Conceptual

advanced

Memory usage comparison for large sparse graph

For a graph with 10,000 vertices and 15,000 edges, which data structure uses less memory?

A Adjacency list because it stores only existing edges

B Adjacency matrix because it uses fixed size memory

C Both use the same amount of memory

D Neither, use edge list for less memory

💡 Hint

Think about how many edges are stored in each structure.

An adjacency matrix for 10,000 vertices uses 100 million entries, which is huge. An adjacency list stores only 15,000 edges, much less memory.

🚀 Application

expert

Choosing data structure for fast edge existence check

You need to frequently check if an edge exists between two vertices in a graph with 500 vertices and 120,000 edges. Which data structure is best?

A Adjacency list because it is memory efficient

B Use a hash map of edges for faster lookups

C Edge list because it is simple to implement

D Adjacency matrix because it allows O(1) edge existence check

💡 Hint

Consider time complexity of checking edge existence.

An adjacency matrix allows constant time O(1) check for edge existence, which is faster than searching adjacency lists or edge lists.

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