Adjacency Matrix Representation in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an adjacency matrix in graph representation?

An adjacency matrix is a 2D array used to represent a graph, where each cell at row i and column j indicates if there is an edge from vertex i to vertex j.

beginner

How do you represent no edge between two vertices in an adjacency matrix for an unweighted graph?

You represent no edge by putting 0 in the cell corresponding to those vertices in the adjacency matrix.

intermediate

In an adjacency matrix for a weighted graph, what value is typically used to represent no edge?

A special value like infinity (or a very large number) is used to represent no edge, depending on the context.

beginner

What is the time complexity to check if an edge exists between two vertices using an adjacency matrix?

It is O(1) because you directly access the cell at row i and column j in the matrix.

intermediate

What is a disadvantage of using adjacency matrix for graph representation?

It uses O(V²) space, which can be inefficient for graphs with many vertices but few edges (sparse graphs).

What does a 1 in the adjacency matrix cell [i][j] represent in an unweighted graph?

A There is an edge from vertex i to vertex j

B There is no edge from vertex i to vertex j

C Vertex i equals vertex j

D The graph is weighted

A 1 means an edge exists from vertex i to vertex j in an unweighted graph.

What is the space complexity of an adjacency matrix for a graph with V vertices?

A O(V²)

B O(V + E)

C O(V)

D O(E²)

An adjacency matrix uses O(V²) space because it stores information for every pair of vertices.

Which operation is fastest with an adjacency matrix?

A Add a new vertex

B List all neighbors of a vertex

C Check if an edge exists between two vertices

D Remove a vertex

Checking if an edge exists is O(1) by directly accessing the matrix cell.

In a weighted graph adjacency matrix, what does a 0 usually mean?

A Edge weight zero

B Graph is unweighted

C Self-loop

D No edge between vertices

0 usually means no edge exists between those vertices.

Which graph type is adjacency matrix less efficient for?

A Dense graphs

B Sparse graphs

C Complete graphs

D Directed graphs

Adjacency matrix is less efficient for sparse graphs because it wastes space storing many zeros.

Explain how an adjacency matrix represents edges in a graph and how to check if an edge exists between two vertices.

Think of a table where rows and columns are vertices and the cell tells if they connect.

Describe the advantages and disadvantages of using an adjacency matrix for graph representation.

Consider speed versus memory use.

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