Adjacency Matrix Representation in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency matrix after adding edges

What is the printed adjacency matrix after adding edges between nodes 0-1, 1-2, and 2-0 in an undirected graph with 3 nodes?

DSA Rust

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

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

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

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

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

💡 Hint

Remember that for an undirected graph, edges are symmetric in the adjacency matrix.

Since the graph is undirected, each edge between nodes i and j is represented by setting graph[i][j] and graph[j][i] to 1. The matrix is symmetric with zeros on the diagonal.

🧠 Conceptual

intermediate

Number of edges in adjacency matrix

Given a directed graph represented by an adjacency matrix of size 4x4, how many edges does the graph have if the matrix has exactly six 1s?

A 4

B 12

C 6

D 8

💡 Hint

Each 1 in the adjacency matrix represents one directed edge.

In a directed graph, each 1 in the adjacency matrix corresponds to one edge from row node to column node. So six 1s mean six edges.

❓ Predict Output

advanced

Output after removing an edge in adjacency matrix

What is the adjacency matrix output after removing the edge from node 1 to node 2 in the following directed graph with 3 nodes?

DSA Rust

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

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

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

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

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

💡 Hint

Setting graph[1][2] to 0 removes the edge from node 1 to node 2.

The original edge from node 1 to node 2 is removed by setting graph[1][2] = 0. The rest of the matrix remains unchanged.

🔧 Debug

advanced

Identify the error in adjacency matrix initialization

What error will this Rust code produce when trying to create an adjacency matrix for 3 nodes? let graph = vec![vec![0; 3]; 3]; graph[0][1] = 1;

DSA Rust

fn main() {
    let graph = vec![vec![0; 3]; 3];
    graph[0][1] = 1;
}

A error[E0596]: cannot assign to `graph[_][_]` because it is not declared as mutable

B error[E0425]: cannot find value `graph` in this scope

C error[E0277]: the trait `Copy` is not implemented for `Vec<i32>`

D no error, code runs successfully

💡 Hint

Check if the variable is mutable before assigning to its elements.

The variable `graph` is declared immutable with `let`. Trying to assign to graph[0][1] causes a compile-time error because the vector is not mutable.

🧠 Conceptual

expert

Memory complexity of adjacency matrix for large sparse graph

What is the memory complexity of storing a graph with 10,000 nodes and 20,000 edges using an adjacency matrix representation?

A O(n^2) where n is the number of nodes, so about 100 million entries

B O(e) where e is the number of edges, so about 20,000 entries

C O(n + e), combining nodes and edges

D O(log n) due to matrix compression

💡 Hint

Adjacency matrix size depends on number of nodes squared, regardless of edges.

An adjacency matrix always requires space proportional to n squared, where n is the number of nodes, because it stores a value for every possible edge.

Practice

1. What does an adjacency matrix represent in graph theory?

easy

A. A list of nodes in the graph

B. A 2D array showing edges between nodes

C. A sequence of visited nodes

D. A stack used for graph traversal

Solution

1. Step 1: Understand adjacency matrix concept

   An adjacency matrix is a 2D array where rows and columns represent nodes.

2. Step 2: Identify what the matrix stores

   Each cell shows if an edge exists between two nodes (1 for edge, 0 for no edge).

3. Final Answer:

   A 2D array showing edges between nodes -> Option B

4. Quick Check:

   Adjacency matrix = 2D edge array [OK]

Hint: Adjacency matrix is always a 2D grid of edges [OK]

Common Mistakes:

• Confusing adjacency matrix with adjacency list
• Thinking it stores node values instead of edges
• Mixing it with traversal order

2. Which Rust code snippet correctly declares a 3x3 adjacency matrix using Vec initialized with zeros?

easy

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

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

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

D. let matrix = [[0, 0, 0], [0, 0, 0]];

Solution

1. Step 1: Understand Rust 2D vector initialization

   Rust uses Vec for dynamic 2D arrays; vec![vec![0; 3]; 3] creates 3 rows of 3 zeros.

2. Step 2: Check each option for correctness

   A: [[0; 3]; 3] creates fixed-size array [[i32;3]; 3], not Vec. B: [0; 3][0; 3] is invalid syntax. D: [[0, 0, 0], [0, 0, 0]] has only 2 rows.

3. Final Answer:

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

4. Quick Check:

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

Hint: Use vec![vec![0; size]; size] for 2D matrix in Rust [OK]

Common Mistakes:

• Using invalid syntax for 2D arrays
• Confusing fixed arrays with vectors
• Incorrect row or column count

3. Given the following Rust code, what is the printed adjacency matrix?

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

medium

A. [1, 0, 0]\n[0, 1, 0]\n[0, 0, 1]

B. [0, 0, 1]\n[1, 0, 0]\n[0, 1, 0]

C. [0, 1, 0]\n[0, 0, 1]\n[0, 0, 0]

D. [0, 1, 1]\n[0, 0, 1]\n[1, 0, 0]

Solution

1. Step 1: Initialize 3x3 zero matrix

   matrix starts as [[0,0,0],[0,0,0],[0,0,0]].

2. Step 2: Update edges as per code

   matrix[0][1] = 1 sets edge from node 0 to 1; matrix[1][2] = 1 sets edge from node 1 to 2.

3. Step 3: Print matrix rows

   Rows print as [0,1,0], [0,0,1], [0,0,0].

4. Final Answer:

   [0, 1, 0]\n[0, 0, 1]\n[0, 0, 0] -> Option C

5. Quick Check:

   Edges at (0,1) and (1,2) = 1 [OK]

Hint: Track each assignment to matrix cells carefully [OK]

Common Mistakes:

• Mixing row and column indices
• Assuming symmetric edges in directed graph
• Printing matrix incorrectly

4. Identify the error in this Rust code for creating an adjacency matrix:

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

medium

A. Index out of bounds error

B. Type mismatch error

C. Syntax error in vector initialization

D. No error, code runs fine

Solution

1. Step 1: Check vector size and indices

   matrix is 3x3 with valid indices 0,1,2 for rows and columns.

2. Step 2: Analyze matrix[3][0] access

   Index 3 is out of bounds for rows (max index 2), causing runtime panic.

3. Final Answer:

   Index out of bounds error -> Option A

4. Quick Check:

   Accessing index 3 in size 3 vector causes error [OK]

Hint: Check indices are within 0 to size-1 [OK]

Common Mistakes:

• Using invalid indices beyond matrix size
• Confusing compile-time and runtime errors
• Ignoring Rust's panic on out-of-bounds

5. You have a directed graph with 4 nodes. Using an adjacency matrix in Rust, how would you represent edges from node 0 to 1 and 2, and from node 3 to 0? Which matrix correctly shows this?

hard

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

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

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

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

Solution

1. Step 1: Understand node indexing and edges

   Nodes are 0 to 3. Edges: 0->1, 0->2, 3->0.

2. Step 2: Map edges to adjacency matrix

   Row 0 has 1s at columns 1 and 2. Row 3 has 1 at column 0. Others are 0.

3. Step 3: Verify options

   [[0, 1, 1, 0], [0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0]] matches this exactly. Others have wrong edges or self loops.

4. Final Answer:

   [[0, 1, 1, 0], [0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0]] -> Option D

5. Quick Check:

   Edges 0->1,0->2 and 3->0 set correctly [OK]

Hint: Rows = from-node, columns = to-node edges [OK]

Common Mistakes:

• Mixing up row and column meaning
• Adding edges not specified
• Confusing directed with undirected edges