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

Concept Flow - Adjacency List vs Matrix When to Choose Which

Start: Need to represent graph

↓

Check graph size and density

↓

Use Adjacency Matrix

↓

Use Adjacency List

↓

Implement chosen representation

↓

Perform graph operations efficiently

Decide graph representation by checking graph size and density, then choose adjacency matrix for small/dense graphs or adjacency list for large/sparse graphs.

Execution Sample

DSA Rust

fn choose_representation(vertices: usize, edges: usize) -> &'static str {
    let max_edges = vertices * (vertices - 1) / 2;
    if edges > max_edges / 2 {
        "Adjacency Matrix"
    } else {
        "Adjacency List"
    }
}

fn main() {
    let choice = choose_representation(5, 6);
    println!("Chosen: {}", choice);
}

This code chooses adjacency matrix if edges are more than half of max possible edges, else adjacency list.

Execution Table

Step	Operation	Vertices	Edges	Max Edges	Condition (edges > max_edges/2)	Chosen Representation
1	Calculate max edges	5	6	10	6 > 5 (True)	Adjacency Matrix
2	Print choice	5	6	10	N/A	Adjacency Matrix
Exit	Decision made based on density	5	6	10	Condition True	Adjacency Matrix

💡 Edges (6) are more than half of max edges (5), so adjacency matrix is chosen.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
vertices	5	5	5	5
edges	6	6	6	6
max_edges	0	10	10	10
condition	N/A	True	True	True
chosen_representation	N/A	Adjacency Matrix	Adjacency Matrix	Adjacency Matrix

Key Moments - 3 Insights

Why do we compare edges to half of max edges?

Because adjacency matrix is efficient for dense graphs, which means many edges. Half of max edges is a simple threshold to decide density, as shown in execution_table step 1.

What happens if the graph is very large but dense?

Adjacency matrix uses more memory but allows fast edge checks. For large dense graphs, matrix is still preferred despite memory cost, as the code chooses matrix when edges exceed half max edges.

Why not always use adjacency list since it saves memory?

Adjacency list is better for sparse graphs but slower for edge checks. The decision in code balances memory and speed by choosing list only when edges are fewer than half max edges.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of max_edges at step 1?

A 5

B 10

C 6

D 15

💡 Hint

Check the 'Max Edges' column in execution_table row for step 1.

At which step does the condition edges > max_edges/2 become true?

A Step 2

B Exit

C Step 1

D Never

💡 Hint

Look at the 'Condition' column in execution_table for step 1.

If edges were 3 instead of 6, what representation would be chosen?

A Adjacency List

B Either one

C Adjacency Matrix

D None

💡 Hint

Refer to variable_tracker 'condition' value and how it affects chosen_representation.

Concept Snapshot

Adjacency List vs Matrix Choice:
- Use adjacency matrix for small or dense graphs.
- Use adjacency list for large or sparse graphs.
- Density threshold often half of max edges.
- Matrix uses more memory but faster edge checks.
- List saves memory but slower for edge lookup.

Full Transcript

This concept helps decide when to use adjacency list or adjacency matrix to represent graphs. We calculate the maximum possible edges for the graph size. If the actual edges are more than half of this maximum, the graph is dense, so adjacency matrix is chosen for faster edge checks despite higher memory use. Otherwise, adjacency list is chosen to save memory for sparse graphs. The example code calculates this and prints the choice. The execution table shows step-by-step how variables change and how the decision is made. Key moments clarify why the half threshold is used and trade-offs between memory and speed. The visual quiz tests understanding of these steps and decisions.

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