Adjacency Matrix Representation in DSA Javascript

Mental Model

An adjacency matrix is a table that shows which nodes in a graph connect to which others using rows and columns.

Analogy: Imagine a city map grid where each row and column is a city, and a mark in the grid shows if there is a direct road between those two cities.

  0 1 2
0 0 1 0
1 1 0 1
2 0 1 0

Rows and columns represent nodes; 1 means connected, 0 means no connection.

Dry Run Walkthrough

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

Goal: Create an adjacency matrix showing connections between nodes

Step 1: Initialize a 3x3 matrix filled with 0s

  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 node 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 are two-way, so mark both directions

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 node 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 are two-way, so mark both directions

Result:

  0 1 2
0 0 1 0
1 1 0 1
2 0 1 0

This matrix shows all connections between nodes.

Annotated Code

DSA Javascript

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

  addEdge(u, v) {
    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));

Create a 2D array filled with zeros to represent no edges initially

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

Mark the presence of an edge from node u to node v

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

Mark the edge in the opposite direction 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(n^2) because we create and print an n by n matrix where n is number of nodes

Space: O(n^2) because the adjacency matrix stores n squared elements

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

Edge Cases

Graph with zero nodes

Creates an empty matrix with no rows or columns

DSA Javascript

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

Graph with one node and no edges

Matrix is 1x1 with zero, showing no self-loop

DSA Javascript

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

Adding edge with invalid node index

Code will throw error or behave unexpectedly (no explicit guard)

DSA Javascript

No explicit guard in addEdge method

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 an undirected graph
Fix: Always set matrix[u][v] and matrix[v][u] to 1 for undirected edges

Mistake: Initializing matrix with wrong dimensions or not filling with zeros
Fix: Use a nested array creation with fill(0) to ensure correct size and initial values

Summary

It represents graph connections using a 2D table where rows and columns are nodes and values show edges.

Use it when you want fast checks if two nodes are connected and the graph is not too large.

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

Practice

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

easy

A. A 2D array showing connections between nodes

B. A list of nodes in the graph

C. A sequence of edges in order

D. A tree structure of nodes

Solution

1. Step 1: Understand adjacency matrix structure

   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 there is a connection (edge) between two nodes.

3. Final Answer:

   A 2D array showing connections between nodes -> Option A

4. Quick Check:

   Adjacency matrix = 2D array of connections [OK]

Hint: Adjacency matrix is always a 2D array of node links [OK]

Common Mistakes:

• Confusing adjacency matrix with adjacency list
• Thinking it stores node values instead of connections
• Assuming it is a sequence or tree

2. Which of the following is the correct way to declare a 3x3 adjacency matrix in JavaScript?

easy

A. const matrix = [0,0,0];

B. const matrix = [[0,0,0],[0,0,0],[0,0,0]];

C. const matrix = new Array(3);

D. const matrix = {0:0,1:0,2:0};

Solution

1. Step 1: Understand adjacency matrix as 2D array

   It must be an array of arrays, each inner array representing a row.

2. Step 2: Check each option's structure

   const matrix = [[0,0,0],[0,0,0],[0,0,0]]; is a 3x3 array filled with zeros, correct for adjacency matrix initialization.

3. Final Answer:

   const matrix = [[0,0,0],[0,0,0],[0,0,0]]; -> Option B

4. Quick Check:

   2D array syntax = const matrix = [[0,0,0],[0,0,0],[0,0,0]]; [OK]

Hint: Adjacency matrix needs nested arrays for rows and columns [OK]

Common Mistakes:

• Using a single array instead of 2D array
• Using object instead of array
• Creating array without inner arrays

3. What is the output of the following code?

const matrix = [
  [0, 1, 0],
  [1, 0, 1],
  [0, 1, 0]
];
console.log(matrix[1][2]);

medium

A. 1

B. 0

C. undefined

D. Error

Solution

1. Step 1: Identify indices in matrix

   matrix[1] is the second row: [1, 0, 1].

2. Step 2: Access element at column 2

   matrix[1][2] is the third element in second row, which is 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   matrix[1][2] = 1 [OK]

Hint: Remember matrix[row][column] indexing starts at 0 [OK]

Common Mistakes:

• Confusing row and column indices
• Assuming 1-based indexing
• Expecting undefined for valid indices

4. Find the error in this adjacency matrix update code:

const matrix = [
  [0, 0],
  [0, 0]
];
matrix[0][1] = 1;
matrix[1][2] = 1;

medium

A. Matrix should be 1D array

B. Cannot assign value to matrix[0][1]

C. Index 2 is out of bounds for matrix[1]

D. No error, code is correct

Solution

1. Step 1: Check matrix dimensions

   Matrix has 2 rows and 2 columns (indices 0 and 1 only).

2. Step 2: Identify invalid index access

   matrix[1][2] tries to access third element in second row, which does not exist.

3. Final Answer:

   Index 2 is out of bounds for matrix[1] -> Option C

4. Quick Check:

   Accessing invalid column index = Error [OK]

Hint: Check array length before accessing indices [OK]

Common Mistakes:

• Ignoring array size limits
• Assuming dynamic resizing on assignment
• Confusing row and column indices

5. Given a graph with 4 nodes, how would you represent an undirected edge between node 1 and node 3 in an adjacency matrix?

hard

A. Set matrix[1][1] = 1 and matrix[3][3] = 1

B. Set matrix[1][3] = 1 only

C. Set matrix[3][1] = 1 only

D. Set matrix[1][3] = 1 and matrix[3][1] = 1

Solution

1. Step 1: Understand undirected edge representation

   Undirected edges are symmetric, so both directions must be marked.

2. Step 2: Mark both connections in matrix

   Set matrix[1][3] = 1 and matrix[3][1] = 1 to show connection both ways.

3. Final Answer:

   Set matrix[1][3] = 1 and matrix[3][1] = 1 -> Option D

4. Quick Check:

   Undirected edge = symmetric matrix entries [OK]

Hint: Undirected edges need two symmetric entries set [OK]

Common Mistakes:

• Setting only one direction for undirected edge
• Setting diagonal elements instead of edge
• Confusing node indices