Adjacency Matrix Representation in DSA Javascript - Execution Trace

Concept Flow - Adjacency Matrix Representation

Start

↓

Create NxN matrix

↓

For each edge

↓

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 Javascript

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

This code shows a 3-node graph adjacency matrix with edges between nodes 0-1 and 1-2.

Execution Table

Step	Operation	Edge Processed	Matrix Update	Matrix State
1	Initialize 3x3 matrix with zeros	None	All zeros	[[0,0,0],[0,0,0],[0,0,0]]
2	Add edge 0->1	(0,1)	matrix[0][1] = 1	[[0,1,0],[0,0,0],[0,0,0]]
3	Add edge 1->0 (undirected)	(1,0)	matrix[1][0] = 1	[[0,1,0],[1,0,0],[0,0,0]]
4	Add edge 1->2	(1,2)	matrix[1][2] = 1	[[0,1,0],[1,0,1],[0,0,0]]
5	Add edge 2->1 (undirected)	(2,1)	matrix[2][1] = 1	[[0,1,0],[1,0,1],[0,1,0]]
6	No more edges	None	No change	[[0,1,0],[1,0,1],[0,1,0]]

💡 All edges processed, adjacency matrix complete

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
matrix	[[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 connections in both directions, as shown in steps 2 and 3.

What does a 0 in the matrix cell mean?

It means there is no direct edge between those two nodes, as seen initially in step 1 and unchanged cells in later steps.

Why is the matrix square and size NxN?

Because each node can connect to every other node including itself, so the matrix must have rows and columns equal to the number of nodes.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the matrix value at position (1,2)?

A 1

B 0

C Undefined

D 2

💡 Hint

Check the 'Matrix Update' and 'Matrix State' columns 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 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look for when matrix[2][1] changes from 0 to 1 in the execution table.

If the graph was directed, which matrix updates would be skipped?

A Step 6 only

B Steps 3 and 5

C Steps 2 and 4

D No steps skipped

💡 Hint

Review which steps add reverse edges in the execution table.

Concept Snapshot

Adjacency Matrix Representation:
- Use an NxN matrix for N nodes
- matrix[u][v] = 1 means edge from u to v
- For undirected graphs, matrix[v][u] = 1 too
- 0 means no edge
- Easy to check edge existence quickly

Full Transcript

Adjacency matrix representation uses a square matrix to show connections between nodes in a graph. Each row and column corresponds to a node. A 1 in matrix[u][v] means there is an edge from node u to node v. For undirected graphs, the matrix is symmetric, so matrix[v][u] is also set to 1. Initially, the matrix is filled with zeros meaning no edges. As edges are processed, the matrix cells are updated to 1 to reflect connections. This method allows quick checks if two nodes are connected by looking at the matrix cell. The matrix size is NxN where N is the number of nodes. This example showed a 3-node graph with edges between nodes 0-1 and 1-2, updating the matrix step-by-step.

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