Adjacency Matrix Representation in DSA Typescript

Mental Model

We use a square grid to show which points connect to which, marking connections with 1 and no connections with 0.

Analogy: Imagine a city map where each intersection is a point, and a big table shows if you can drive directly from one intersection to another by marking yes or no.

   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: Create a matrix showing which nodes connect directly

Step 1: Start with a 3x3 matrix filled with zeros

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

Why: We need a blank grid to mark connections

Step 2: Mark connection from node 0 to node 1 with 1

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

Why: Node 0 connects to node 1

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

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

Why: Node 1 connects back to node 0

Step 4: Mark connection from node 1 to node 2 with 1

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

Why: Node 1 connects to node 2

Step 5: Mark connection from node 2 to node 1 with 1

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

Why: Node 2 connects back to node 1

Result:

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

Annotated Code

DSA Typescript

class Graph {
  matrix: number[][];
  size: number;

  constructor(size: number) {
    this.size = size;
    this.matrix = Array.from({ length: size }, () => Array(size).fill(0));
  }

  addEdge(u: number, v: number) {
    this.matrix[u][v] = 1; // mark edge from u to v
    this.matrix[v][u] = 1; // mark edge from v to u (undirected)
  }

  printMatrix() {
    for (let i = 0; i < this.size; i++) {
      console.log(this.matrix[i].join(' '));
    }
  }
}

// Driver code
const graph = new Graph(3);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.printMatrix();

this.matrix = Array.from({ length: size }, () => Array(size).fill(0));

Initialize a size x size matrix filled with zeros

this.matrix[u][v] = 1; // mark edge from u to v

Mark connection from node u to node v

this.matrix[v][u] = 1; // mark edge from v to u (undirected)

Mark connection from node v to node u for undirected graph

console.log(this.matrix[i].join(' '));

Print each row of the adjacency matrix

Output

0 1 0

1 0 1

0 1 0

Complexity Analysis

Time: O(1) per edge insertion because we directly access matrix 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

Matrix is empty, no edges to add

DSA Typescript

this.matrix = Array.from({ length: size }, () => Array(size).fill(0));

Graph with one node and no edges

Matrix is 1x1 with zero, no edges marked

DSA Typescript

this.matrix = Array.from({ length: size }, () => Array(size).fill(0));

Adding edge with invalid node index

Code may throw error or ignore, no explicit guard in code

When to Use This Pattern

When you need to quickly check if two nodes connect directly and have a small graph, use adjacency matrix for constant-time edge lookup.

Common Mistakes

Mistake: Forgetting to mark both [u][v] and [v][u] for undirected graphs
Fix: Always set matrix[u][v] and matrix[v][u] to 1 to represent undirected edges

Summary

It stores graph connections in a 2D grid marking edges with 1 and no edges with 0.

Use it when the graph is small or you need fast edge existence checks.

The key is that each cell directly shows if two nodes connect, making lookups instant.