Adjacency Matrix Representation in DSA Rust - Execution Trace

Concept Flow - Adjacency Matrix Representation

Start

↓

Create NxN matrix

↓

Initialize all cells to 0

↓

For each edge (u,v)

↓

Set matrix[u

↓

If undirected, set matrix[v

↓

Matrix represents graph connections

↓

End

We create a square matrix where each cell shows if two nodes are connected by an edge.

Execution Sample

DSA Rust

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

This code creates a 4x4 matrix and marks edges between nodes 0-1, 1-2, 2-3, and 3-0.

Execution Table

Step	Operation	Matrix State	Pointer Changes	Visual State
1	Create 4x4 matrix initialized to 0	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	matrix points to new 4x4 zero matrix	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2	Add edge 0->1	[[0,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	matrix[0][1] set to 1	0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3	Add edge 1->2	[[0,1,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	matrix[1][2] set to 1	0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0
4	Add edge 2->3	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]]	matrix[2][3] set to 1	0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
5	Add edge 3->0	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	matrix[3][0] set to 1	0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
6	End	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	No pointer changes	0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0

💡 All edges added, matrix fully represents graph connections.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
matrix	undefined	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]

Key Moments - 3 Insights

Why do we initialize the matrix with zeros before adding edges?

Because zeros mean no connection between nodes. The execution_table step 1 shows the matrix full of zeros before edges are added.

Why do we set matrix[u][v] = 1 for an edge from u to v?

Because 1 means there is a connection from node u to node v. See execution_table steps 2 to 5 where each edge sets a 1 in the matrix.

What if the graph is undirected? How does the matrix change?

For undirected graphs, we set both matrix[u][v] and matrix[v][u] to 1. This is not shown here but would mean symmetric entries in the matrix.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of matrix[1][2]?

A 1

B 0

C Undefined

D 2

💡 Hint

Check the 'Matrix State' column at step 3 in the execution_table.

At which step does the matrix first show a connection from node 3 to node 0?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Operation' and 'Matrix State' columns in the execution_table for when matrix[3][0] changes.

If we wanted to represent an undirected edge between nodes 0 and 1, what changes would we make?

A Set matrix[0][1] = 1 only

B Set both matrix[0][1] and matrix[1][0] to 1

C Set matrix[1][0] = 1 only

D No changes needed

💡 Hint

Refer to key_moments about undirected graphs and symmetric matrix entries.

Concept Snapshot

Adjacency Matrix Representation:
- Use an NxN matrix for N nodes
- matrix[i][j] = 1 means edge from i to j
- Initialize all cells to 0 (no edges)
- For undirected graphs, matrix is symmetric
- Easy to check if edge exists in O(1) time

Full Transcript

Adjacency Matrix Representation uses a square matrix to show connections between nodes. We start by creating an NxN matrix filled with zeros, meaning no edges. Then for each edge from node u to node v, we set matrix[u][v] to 1. If the graph is undirected, we also set matrix[v][u] to 1 to keep symmetry. This method allows quick checks if two nodes are connected by looking at the matrix cell. The example code creates a 4x4 matrix and adds edges between nodes 0-1, 1-2, 2-3, and 3-0. The execution table shows the matrix state after each edge is added, helping visualize how the graph builds up step-by-step.

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