Adjacency Matrix Representation in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency matrix after adding edges

What is the printed adjacency matrix after adding edges between nodes 0-1, 1-2, and 2-0 in an undirected graph of 3 nodes?

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

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

A

0 0 0
0 0 0
0 0 0

B

0 1 0
1 0 1
0 1 0

C

1 1 1
1 1 1
1 1 1

D

0 1 1
1 0 1
1 1 0

💡 Hint

Think about how undirected edges are represented symmetrically in the matrix.

Each edge between nodes u and v sets matrix[u][v] and matrix[v][u] to 1. Since edges are between 0-1, 1-2, and 2-0, the matrix is symmetric with 1s at those positions.

❓ Predict Output

intermediate

Output after removing an edge in adjacency matrix

What is the adjacency matrix output after removing the edge between nodes 1 and 2 from the previous graph?

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;
    this.matrix[v][u] = 1;
  }
  removeEdge(u: number, v: number) {
    this.matrix[u][v] = 0;
    this.matrix[v][u] = 0;
  }
  printMatrix() {
    for (let i = 0; i < this.size; i++) {
      console.log(this.matrix[i].join(' '));
    }
  }
}

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

A

0 0 0
0 0 0
0 0 0

B

0 1 1
1 0 1
1 1 0

C

0 1 1
1 0 0
1 0 0

D

1 1 1
1 1 1
1 1 1

💡 Hint

Removing an edge sets the corresponding matrix entries to zero.

Removing edge 1-2 sets matrix[1][2] and matrix[2][1] to 0, while other edges remain.

🔧 Debug

advanced

Identify the error in adjacency matrix initialization

What error will this code produce when creating an adjacency matrix for 3 nodes?

DSA Typescript

class Graph {
  matrix: number[][];
  size: number;
  constructor(size: number) {
    this.size = size;
    this.matrix = Array(size).fill(Array(size).fill(0));
  }
}

const g = new Graph(3);
g.matrix[0][1] = 1;
console.log(g.matrix);

A All rows change when one element is updated because inner arrays are shared

B TypeError because matrix is undefined

C SyntaxError due to missing semicolon

D No error, matrix updates correctly

💡 Hint

Check how Array.fill works with objects inside.

Using Array.fill with an array fills all positions with the same reference, so changing one row changes all rows.

❓ Predict Output

advanced

Output of adjacency matrix for directed graph

What is the adjacency matrix output after adding directed edges 0->1, 1->2, and 2->0 in a graph of 3 nodes?

DSA Typescript

class DirectedGraph {
  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;
  }
  printMatrix() {
    for (let i = 0; i < this.size; i++) {
      console.log(this.matrix[i].join(' '));
    }
  }
}

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

A

0 1 0
0 0 1
1 0 0

B

0 1 1
1 0 1
1 1 0

C

0 0 0
0 0 0
0 0 0

D

1 0 0
0 1 0
0 0 1

💡 Hint

Directed edges only set one direction in the matrix.

Each directed edge sets matrix[u][v] to 1 only, so the matrix is not symmetric.

🧠 Conceptual

expert

Memory complexity of adjacency matrix vs adjacency list

Which statement correctly compares the memory usage of adjacency matrix and adjacency list for a graph with V vertices and E edges?

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

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

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

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

💡 Hint

Think about how adjacency matrix stores all possible edges.

Adjacency matrix always stores V x V entries, so O(V^2). Adjacency list stores only existing edges plus vertices, so O(V + E).