Adjacency List vs Matrix When to Choose Which in DSA Rust - Build Both Approaches

Adjacency List vs Matrix When to Choose Which

📖 Scenario: Imagine you are organizing a small social network of friends. You want to keep track of who is friends with whom. You can store this information in two ways: using an adjacency list or an adjacency matrix. Each way has its own advantages depending on how many friends each person has.

🎯 Goal: Build two simple graph representations for the same set of friends: one using an adjacency list and one using an adjacency matrix. Learn when to use each method by comparing their structures.

📋 What You'll Learn

Create an adjacency list for a graph with 4 friends and their connections

Create an adjacency matrix for the same graph

Use a variable to store the number of friends

Print both the adjacency list and adjacency matrix to compare

💡 Why This Matters

🌍 Real World

Social networks, maps, and computer networks use graphs to represent connections between people, places, or devices.

💼 Career

Understanding graph representations helps in software development, especially in areas like networking, recommendation systems, and data analysis.

1

Create the adjacency list for the graph

Create a variable called adj_list as a Vec> representing the friends and their connections exactly as: friend 0 connected to 1 and 2, friend 1 connected to 0 and 3, friend 2 connected to 0, friend 3 connected to 1.

DSA Rust

# Your code here

Hint

Use a vector of vectors where each inner vector lists the friends connected to that friend.

2

Create a variable for the number of friends

Add a variable called num_friends of type usize and set it to 4 to represent the total number of friends.

DSA Rust

fn main() {
    let adj_list: Vec> = vec![
        vec![1, 2], // friend 0 connected to 1 and 2
        vec![0, 3], // friend 1 connected to 0 and 3
        vec![0],    // friend 2 connected to 0
        vec![1],    // friend 3 connected to 1
    ];
    
    // Your code here
}

Hint

Use let num_friends: usize = 4; to store the number of friends.

3

Create the adjacency matrix for the graph

Create a variable called adj_matrix as a Vec> representing the connections between friends using a 4x4 matrix. Use 1 for connected and 0 for not connected. The matrix rows and columns represent friends 0 to 3 in order, with connections matching the adjacency list.

DSA Rust

fn main() {
    let adj_list: Vec> = vec![
        vec![1, 2], // friend 0 connected to 1 and 2
        vec![0, 3], // friend 1 connected to 0 and 3
        vec![0],    // friend 2 connected to 0
        vec![1],    // friend 3 connected to 1
    ];
    
    let num_friends: usize = 4;

    // Your code here
}

Hint

Use a 4x4 vector of vectors with 1s and 0s to show connections between friends.

4

Print both adjacency list and matrix

Print the adj_list and adj_matrix variables using println! to show their contents for comparison.

DSA Rust

fn main() {
    let adj_list: Vec> = vec![
        vec![1, 2], // friend 0 connected to 1 and 2
        vec![0, 3], // friend 1 connected to 0 and 3
        vec![0],    // friend 2 connected to 0
        vec![1],    // friend 3 connected to 1
    ];
    
    let num_friends: usize = 4;

    let adj_matrix: Vec> = vec![
        vec![0, 1, 1, 0], // friend 0 connections
        vec![1, 0, 0, 1], // friend 1 connections
        vec![1, 0, 0, 0], // friend 2 connections
        vec![0, 1, 0, 0], // friend 3 connections
    ];

    // Your code here
}

Hint

Use println!("Adjacency List: {:?}", adj_list); and a for loop to print each row of adj_matrix.

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