Adjacency Matrix Representation in DSA Typescript - 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

↓

Repeat for all edges

↓

Adjacency matrix ready

Build a square matrix where each cell shows if an edge exists between two nodes.

Execution Sample

DSA Typescript

const graph = [
  [0, 1, 0],
  [1, 0, 1],
  [0, 1, 0]
];

This code creates a 3-node graph adjacency matrix showing edges between nodes.

Execution Table

Step	Operation	Matrix State	Pointer Changes	Visual State
1	Create 3x3 matrix	[[0,0,0],[0,0,0],[0,0,0]]	matrix initialized	0 0 0 0 0 0 0 0 0
2	Add edge 0->1	[[0,1,0],[0,0,0],[0,0,0]]	matrix[0][1] = 1	0 1 0 0 0 0 0 0 0
3	Add edge 1->0 (undirected)	[[0,1,0],[1,0,0],[0,0,0]]	matrix[1][0] = 1	0 1 0 1 0 0 0 0 0
4	Add edge 1->2	[[0,1,0],[1,0,1],[0,0,0]]	matrix[1][2] = 1	0 1 0 1 0 1 0 0 0
5	Add edge 2->1 (undirected)	[[0,1,0],[1,0,1],[0,1,0]]	matrix[2][1] = 1	0 1 0 1 0 1 0 1 0
6	All edges added	[[0,1,0],[1,0,1],[0,1,0]]	no pointer changes	0 1 0 1 0 1 0 1 0

💡 All edges processed, adjacency matrix fully built

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,1,0],[0,0,0],[0,0,0]]	[[0,1,0],[1,0,0],[0,0,0]]	[[0,1,0],[1,0,1],[0,0,0]]	[[0,1,0],[1,0,1],[0,1,0]]	[[0,1,0],[1,0,1],[0,1,0]]

Key Moments - 3 Insights

Why do we set both matrix[u][v] and matrix[v][u] for undirected graphs?

Because undirected edges connect nodes both ways, so the matrix must reflect edges in both directions, as shown in steps 2 and 3.

What does a 0 or 1 in the matrix cell mean?

0 means no edge between nodes, 1 means an edge exists. This is clear in the matrix states in the execution table.

Why is the matrix square (NxN)?

Because it represents all possible connections between N nodes, each row and column corresponds to a node.

Visual Quiz - 3 Questions

Look at the execution table at Step 4, what is the value of matrix[1][2]?

A 0

B 1

C undefined

D 2

💡 Hint

Check the 'Matrix State' column at Step 4 in the execution table.

At which step does the matrix first show an edge from node 2 to node 1?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for matrix[2][1] = 1 in the 'Matrix State' column in the execution table.

If the graph was directed, which steps would be skipped?

A Steps 3 and 5

B Steps 2 and 4

C Step 6 only

D No steps skipped

💡 Hint

Undirected graphs add edges in both directions, see steps 3 and 5 for reverse edges.

Concept Snapshot

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

Full Transcript

Adjacency matrix representation uses a square matrix to show connections between nodes. Each cell matrix[i][j] is 1 if there is an edge from node i to node j, else 0. For undirected graphs, edges are added in both directions making the matrix symmetric. The execution table shows step-by-step how edges are added and how the matrix changes. This method allows quick edge checks but uses O(N^2) space.