Adjacency Matrix Representation in DSA Rust

Mental Model

We use a square grid of numbers to show which points connect to which in a network.

Analogy: Imagine a city map with intersections as points and roads as connections. The grid tells you if a road exists between two intersections.

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Dry Run Walkthrough

Input: Graph with 3 nodes: edges between 0-1 and 1-2

Goal: Show the adjacency matrix that marks connections between nodes

Step 1: Create a 3x3 matrix filled with zeros

   0 1 2
0 [0 0 0]
1 [0 0 0]
2 [0 0 0]

Why: Start with no connections marked

Step 2: Mark connection from node 0 to node 1

   0 1 2
0 [0 1 0]
1 [0 0 0]
2 [0 0 0]

Why: Indicate edge from 0 to 1

Step 3: Mark connection from node 1 to node 0 (undirected graph)

   0 1 2
0 [0 1 0]
1 [1 0 0]
2 [0 0 0]

Why: Edges go both ways in undirected graph

Step 4: Mark connection from node 1 to node 2

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 0 0]

Why: Add edge from 1 to 2

Step 5: Mark connection from node 2 to node 1 (undirected graph)

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Why: Edges go both ways in undirected graph

Result:

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Annotated Code

DSA Rust

struct Graph {
    adjacency_matrix: Vec<Vec<u8>>,
    size: usize,
}

impl Graph {
    fn new(size: usize) -> Self {
        Self {
            adjacency_matrix: vec![vec![0; size]; size],
            size,
        }
    }

    fn add_edge(&mut self, u: usize, v: usize) {
        // mark edge from u to v
        self.adjacency_matrix[u][v] = 1;
        // mark edge from v to u for undirected graph
        self.adjacency_matrix[v][u] = 1;
    }

    fn print_matrix(&self) {
        for row in &self.adjacency_matrix {
            for val in row {
                print!("{} ", val);
            }
            println!();
        }
    }
}

fn main() {
    let mut graph = Graph::new(3);
    graph.add_edge(0, 1);
    graph.add_edge(1, 2);
    graph.print_matrix();
}

self.adjacency_matrix[u][v] = 1;

mark edge from node u to node v

self.adjacency_matrix[v][u] = 1;

mark edge from node v to node u for undirected graph

for row in &self.adjacency_matrix {

iterate over each row to print matrix

for val in row {

iterate over each value in row to print

Output

0 1 0 

1 0 1 

0 1 0 

Complexity Analysis

Time: O(1) for adding an edge because we directly access matrix cells; O(n^2) to print because we visit all cells

Space: O(n^2) because we store a matrix of size n by n for n nodes

vs Alternative: Compared to adjacency lists which use O(n + e) space, adjacency matrix uses more space but allows faster edge checks

Edge Cases

Empty graph with zero nodes

Creates an empty matrix with no rows or columns

DSA Rust

Self { adjacency_matrix: vec![vec![0; size]; size], size }

Graph with one node and no edges

Matrix is 1x1 with zero indicating no self-loop

DSA Rust

Self { adjacency_matrix: vec![vec![0; size]; size], size }

Adding edge with invalid node index

Program may panic or error due to out-of-bounds access (not handled)

DSA Rust

None (no explicit guard in code)

When to Use This Pattern

When you need to quickly check if two nodes are connected and the graph is small or dense, use adjacency matrix because it gives O(1) edge lookup.

Common Mistakes

Mistake: Forgetting to mark both directions in undirected graph
Fix: Always set adjacency_matrix[u][v] and adjacency_matrix[v][u] to 1

Mistake: Using adjacency matrix for very large sparse graphs causing high memory use
Fix: Use adjacency list representation for large sparse graphs

Summary

It stores graph connections in a square grid where each cell shows if two nodes connect.

Use it when the graph is small or you need fast checks if nodes connect.

The key is that each cell directly answers if an edge exists between two nodes.

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