Adjacency Matrix Representation in DSA C# - Execution Trace

Concept Flow - Adjacency Matrix Representation

Start

↓

Create NxN matrix

↓

Initialize all cells to 0

↓

For each edge (u,v)

↓

Set matrix[u,v

↓

If undirected, set matrix[v,u

↓

Repeat for all edges

↓

Adjacency matrix ready

Create a square matrix for all nodes, mark 1 where edges exist, 0 otherwise.

Execution Sample

DSA C#

int[,] matrix = new int[4,4];
matrix[0,1] = 1;
matrix[1,2] = 1;
matrix[2,3] = 1;
matrix[3,0] = 1;

Build a 4-node graph adjacency matrix with edges 0->1, 1->2, 2->3, 3->0.

Execution Table

Step	Operation	Matrix State	Pointer Changes	Visual State
1	Create 4x4 matrix	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	matrix created	Empty 4x4 matrix with all zeros
2	Add edge 0->1	[[0,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	matrix[0,1] = 1	Mark 1 at row 0, col 1
3	Add edge 1->2	[[0,1,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	matrix[1,2] = 1	Mark 1 at row 1, col 2
4	Add edge 2->3	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]]	matrix[2,3] = 1	Mark 1 at row 2, col 3
5	Add edge 3->0	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	matrix[3,0] = 1	Mark 1 at row 3, col 0
6	End	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	No changes	Final adjacency matrix

💡 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	null	[[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. This is shown in Step 1 of the execution_table where the matrix is all zeros before edges are added.

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

Because 1 indicates a direct connection from node u to node v. This is shown in Steps 2 to 5 where each edge sets a 1 in the matrix.

How would the matrix change if the graph was undirected?

For each edge u->v, we would also set matrix[v,u] = 1. This means the matrix would be symmetric. The current table only sets one direction.

Visual Quiz - 3 Questions

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

A 0

B 1

C 2

D Undefined

💡 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 1

💡 Hint

Look for matrix[3,0] = 1 in the 'Matrix State' column in the execution_table.

If the graph was undirected, what additional change would happen at Step 2?

A matrix[1,0] = 1 would be set

B matrix[0,1] = 0 would be set

C No change needed

D matrix[2,1] = 1 would be set

💡 Hint

For undirected graphs, edges go both ways, so the opposite cell is also set.

Concept Snapshot

Adjacency Matrix Representation:
- Use a 2D NxN matrix for N nodes
- matrix[u,v] = 1 means edge from u to v
- 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 show the two-way connection. This method makes it easy to check if two nodes are connected by looking at one cell in the matrix. The example builds a 4-node graph with edges 0->1, 1->2, 2->3, and 3->0, updating the matrix step-by-step.

Practice

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

easy

A. A queue of nodes to visit

B. A list of nodes in the graph

C. A 2D array showing edges between nodes

D. A stack of visited nodes

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 C

4. Quick Check:

   Adjacency matrix = 2D array of edges [OK]

Hint: Adjacency matrix is always a 2D array showing connections [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare an adjacency matrix for 4 nodes in C#?

easy

A. int[] matrix = new int[4];

B. int[,] matrix = new int[4,4];

C. int[][] matrix = new int[4];

D. int matrix = new int[4,4];

Solution

1. Step 1: Identify correct 2D array syntax in C#

   In C#, a 2D array is declared as int[,] with size [rows, columns].

2. Step 2: Check each option

   int[,] matrix = new int[4,4]; uses int[,] with size [4,4], correct for adjacency matrix of 4 nodes.

3. Final Answer:

   int[,] matrix = new int[4,4]; -> Option B

4. Quick Check:

   2D array syntax = int[,] [OK]

Hint: Use int[,] for 2D arrays in C# [OK]

Common Mistakes:

• Using jagged array syntax instead of 2D array
• Declaring 1D array for adjacency matrix
• Missing comma in array declaration

3. Given the following adjacency matrix for a graph with 3 nodes:

int[,] matrix = new int[,] {
  {0, 1, 0},
  {1, 0, 1},
  {0, 1, 0}
};

What is the output of Console.WriteLine(matrix[1,2]);?

medium

A. 1

B. 0

C. 2

D. Error

Solution

1. Step 1: Locate matrix element at row 1, column 2

   Matrix rows and columns start at 0, so matrix[1,2] is second row, third column.

2. Step 2: Check value at matrix[1,2]

   From the matrix, second row is {1, 0, 1}, third element is 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   matrix[1,2] = 1 [OK]

Hint: Remember zero-based indexing for matrix rows and columns [OK]

Common Mistakes:

• Confusing row and column indices
• Assuming 1-based indexing
• Misreading matrix values

4. Identify the error in this C# code snippet for creating an adjacency matrix of 3 nodes:

int[] matrix = new int[3];
matrix[0,1] = 1;

medium

A. Incorrect array declaration syntax

B. No error, code is correct

C. Index out of range error

D. Cannot assign value to matrix[0,1]

Solution

1. Step 1: Analyze array declaration

   int[] matrix = new int[3]; declares a 1D array of 3 integers.

2. Step 2: Examine the assignment

   matrix[0,1] = 1; attempts to use 2D indexing on a 1D array, which is invalid in C#.

3. Final Answer:

   Cannot assign value to matrix[0,1] -> Option D

4. Quick Check:

   1D array indexing mismatch [OK]

Hint: 1D arrays cannot use [row,col] indexing [OK]

Common Mistakes:

• Using 2D indexing on 1D array
• Assuming jagged array syntax for 2D array
• Ignoring compiler error messages

5. You have a directed graph with 4 nodes. Which adjacency matrix correctly represents edges from node 0 to 1 and 2, and from node 3 to 0?

hard

A. int[,] matrix = new int[,] {
{0, 1, 1, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{1, 0, 0, 0}
};

B. int[,] matrix = new int[,] {
{0, 1, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0},
{0, 0, 0, 1}
};

C. int[,] matrix = new int[,] {
{0, 0, 0, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{0, 1, 1, 0}
};

D. int[,] matrix = new int[,] {
{0, 1, 1, 0},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 0}
};

Solution

1. Step 1: Understand directed edges in adjacency matrix

   For directed graph, matrix[i,j] = 1 means edge from node i to node j.

2. Step 2: Check edges from node 0 to 1 and 2

   Row 0 should have 1s at columns 1 and 2.

3. Step 3: Check edge from node 3 to 0

   Row 3 should have 1 at column 0.

4. Step 4: Verify options

   int[,] matrix = new int[,] { {0, 1, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {1, 0, 0, 0} }; matches all conditions exactly.

5. Final Answer:

   {{0, 1, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {1, 0, 0, 0}} -> Option A

6. Quick Check:

   Directed edges = matrix[i,j] = 1 [OK]

Hint: Row = from node, column = to node in adjacency matrix [OK]

Common Mistakes:

• Confusing rows and columns for direction
• Using symmetric matrix for directed graph
• Missing edges or adding extra edges