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

↓

If undirected graph, set matrix[v

↓

Matrix ready to represent graph

↓

Use matrix for graph operations

↓

End

Create a square matrix with size equal to number of nodes, fill with zeros, then mark edges by setting 1s at corresponding positions.

Execution Sample

DSA C

int graph[4][4] = {0};
graph[0][1] = 1;
graph[1][2] = 1;
graph[2][3] = 1;
graph[3][0] = 1;

This code creates a 4-node graph and marks edges between nodes using an adjacency matrix.

Execution Table

Step	Operation	Matrix State	Pointer Changes	Visual State
1	Initialize 4x4 matrix with zeros	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	None	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]]	graph[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]]	graph[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]]	graph[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]]	graph[3][0] set to 1	0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
6	End of edge additions	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	None	Final matrix represents graph edges

💡 All edges added, matrix fully represents the graph

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
graph	[[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 entire matrix with zeros before adding edges?

Because the matrix must start with no connections; zeros mean no edges. This is shown in Step 1 of the execution_table where the matrix is all zeros before edges are added.

Why do we set graph[u][v] = 1 to represent an edge?

Setting graph[u][v] = 1 marks that there is a direct edge from node u to node v. This is shown in Steps 2 to 5 where each edge updates one cell to 1.

How does the matrix represent direction in the graph?

The row index is the start node and the column index is the end node. So graph[u][v] = 1 means edge from u to v. For example, Step 2 sets graph[0][1] = 1 meaning edge from node 0 to node 1.

Visual Quiz - 3 Questions

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

A 1

B 2

C 0

D Undefined

💡 Hint

Check the 'Matrix State' column at Step 3 in the execution_table

At which step does the matrix first show an edge from node 3 to node 0?

A Step 3

B Step 5

C Step 2

D Step 4

💡 Hint

Look for graph[3][0] = 1 in the 'Matrix State' column in execution_table

If we add an edge from node 1 to node 0 in this matrix, what will change?

A graph[0][1] will become 0

B graph[1][2] will become 0

C graph[1][0] will become 1

D No change in matrix

💡 Hint

Adding edge 1->0 means setting graph[1][0] = 1, check variable_tracker for similar updates

Concept Snapshot

Adjacency Matrix Representation:
- Use NxN matrix for N nodes
- Initialize all cells to 0 (no edges)
- For edge u->v, set matrix[u][v] = 1
- For undirected graphs, also set matrix[v][u] = 1
- Easy to check if edge exists by matrix[u][v]
- Uses O(N^2) space regardless of edges

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. This marks the presence of that edge. The matrix rows represent start nodes and columns represent end nodes, so direction is clear. The execution table shows step-by-step how edges are added and how the matrix changes. This method uses more space but makes checking edges very fast.