Adjacency Matrix Representation in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency matrix after adding edges

What is the printed adjacency matrix after running the following code that adds edges to a graph with 3 nodes?

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;
    this.matrix[v][u] = 1;
  }
  printMatrix() {
    for (let row of this.matrix) {
      console.log(row.join(' '));
    }
  }
}

const g = new Graph(3);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.printMatrix();

A

0 1 0
1 0 1
0 1 0

B

0 0 0
0 0 0
0 0 0

C

0 1 1
1 0 1
1 1 0

D

1 1 0
1 1 1
0 1 1

💡 Hint

Remember that addEdge marks both [u][v] and [v][u] as 1 for an undirected graph.

The graph has 3 nodes. Edges are added between 0-1 and 1-2. So matrix[0][1] and matrix[1][0] are 1, and matrix[1][2] and matrix[2][1] are 1. All other entries remain 0.

❓ Predict Output

intermediate

Adjacency matrix after removing an edge

What is the output adjacency matrix after removing the edge between nodes 1 and 2 in the following 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;
    this.matrix[v][u] = 1;
  }
  removeEdge(u, v) {
    this.matrix[u][v] = 0;
    this.matrix[v][u] = 0;
  }
  printMatrix() {
    for (let row of this.matrix) {
      console.log(row.join(' '));
    }
  }
}

const g = new Graph(3);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.removeEdge(1, 2);
g.printMatrix();

A

0 1 0
1 0 0
0 0 0

B

0 1 0
1 0 1
0 1 0

C

0 0 0
0 0 0
0 0 0

D

1 1 0
1 1 1
0 1 1

💡 Hint

Removing edge sets the corresponding entries to 0.

Edges 0-1 and 1-2 were added, then edge 1-2 was removed. So only edge 0-1 remains.

🧠 Conceptual

advanced

Memory usage of adjacency matrix vs adjacency list

Which statement correctly describes the memory usage difference between adjacency matrix and adjacency list for a graph with V vertices and E edges?

A Adjacency matrix uses O(V + E) memory; adjacency list uses O(V^2) memory.

B Both adjacency matrix and adjacency list use O(V^2) memory.

C Adjacency matrix always uses O(V^2) memory regardless of edges; adjacency list uses O(V + E) memory.

D Adjacency matrix uses O(E) memory; adjacency list uses O(V) memory.

💡 Hint

Think about how adjacency matrix stores all possible edges.

Adjacency matrix stores a V by V matrix, so memory is O(V^2). Adjacency list stores only existing edges, so memory is O(V + E).

❓ Predict Output

advanced

Output after checking edge existence

What is the output of the following code that checks if an edge exists between nodes 0 and 2?

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;
    this.matrix[v][u] = 1;
  }
  hasEdge(u, v) {
    return this.matrix[u][v] === 1;
  }
}

const g = new Graph(3);
g.addEdge(0, 1);
g.addEdge(1, 2);
console.log(g.hasEdge(0, 2));

A true

B false

C undefined

D TypeError

💡 Hint

Edge 0-2 was never added.

Edges added are 0-1 and 1-2. Edge 0-2 does not exist, so hasEdge returns false.

🧠 Conceptual

expert

Time complexity of checking edge existence in adjacency matrix

What is the time complexity to check if an edge exists between two nodes in an adjacency matrix representation of a graph with V vertices?

A O(log V) logarithmic time

B O(V) linear time

C O(E) proportional to edges

D O(1) constant time

💡 Hint

Adjacency matrix stores direct access to edges.

Checking edge existence is a direct lookup in the matrix at [u][v], which is constant time O(1).

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