Adjacency List vs Matrix When to Choose Which in DSA Rust - Key Differences

Recall & Review

beginner

What is an adjacency list in graph representation?

An adjacency list stores each node with a list of its connected neighbors. It uses less space for sparse graphs and is efficient for iterating over neighbors.

beginner

What is an adjacency matrix in graph representation?

An adjacency matrix is a 2D array where each cell (i, j) shows if there is an edge between node i and node j. It uses more space but allows quick edge checks.

intermediate

When should you choose an adjacency list over an adjacency matrix?

Choose adjacency list when the graph is sparse (few edges) because it saves memory and is faster to traverse neighbors.

intermediate

When is an adjacency matrix a better choice?

Use adjacency matrix for dense graphs (many edges) or when you need to quickly check if an edge exists between two nodes.

intermediate

What is the space complexity difference between adjacency list and adjacency matrix?

Adjacency list uses O(V + E) space (V = vertices, E = edges), while adjacency matrix uses O(V²) space regardless of edges.

Which graph representation is more memory efficient for a graph with 1000 nodes and 10 edges?

A None of the above

B Adjacency matrix

C Adjacency list

D Both use the same memory

Adjacency list uses memory proportional to edges, so it is more efficient for sparse graphs like this.

Which representation allows O(1) time to check if an edge exists between two nodes?

A Adjacency list

B Adjacency matrix

C Both have O(1) time

D Neither has O(1) time

Adjacency matrix stores edges in a 2D array, so checking an edge is a direct lookup.

For a dense graph, which representation is generally preferred?

A Adjacency matrix

B Adjacency list

C Linked list

D Edge list

Dense graphs have many edges, so adjacency matrix is preferred for quick edge checks.

What is the main disadvantage of adjacency matrix for large sparse graphs?

A Slow edge lookup

B Cannot represent directed edges

C Complex implementation

D High memory usage

Adjacency matrix uses O(V²) space, which is large for sparse graphs.

Which representation is better for iterating over all neighbors of a node?

A Adjacency list

B Adjacency matrix

C Both are equally efficient

D Neither is efficient

Adjacency list stores neighbors directly, making iteration faster and simpler.

Explain when to use adjacency list versus adjacency matrix for graph representation.

Think about how many edges the graph has and what operations you need to do quickly.

Describe the space complexity of adjacency list and adjacency matrix and why it matters.

Consider how the number of edges affects memory use.

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