Adjacency Matrix Representation in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an adjacency matrix in graph representation?

An adjacency matrix is a 2D array used to represent a graph, where each cell at row i and column j indicates if there is an edge between vertex i and vertex j.

beginner

How do you represent no edge between two vertices in an adjacency matrix?

You represent no edge by placing 0 (zero) in the matrix cell corresponding to those vertices.

beginner

What is the size of an adjacency matrix for a graph with n vertices?

The adjacency matrix size is n x n, where n is the number of vertices in the graph.

intermediate

How does an adjacency matrix represent an undirected graph?

In an undirected graph, the adjacency matrix is symmetric, meaning the value at [i][j] is the same as at [j][i].

intermediate

What is a disadvantage of using adjacency matrices for sparse graphs?

Adjacency matrices use a lot of memory for sparse graphs because they store all possible edges, even if many do not exist.

What value is stored in an adjacency matrix cell if there is an edge between vertex 2 and vertex 3?

A 1

B 0

C -1

D null

A value of 1 indicates an edge exists between the two vertices.

What is the time complexity to check if an edge exists between two vertices in an adjacency matrix?

A O(n)

B O(n^2)

C O(1)

D O(log n)

Checking an edge is direct access in the matrix, so it takes constant time O(1).

Which graph type usually wastes memory when using adjacency matrices?

A Sparse graph

B Complete graph

C Directed graph

D Weighted graph

Sparse graphs have few edges, so adjacency matrices waste memory storing many zeros.

In an undirected graph's adjacency matrix, what is true about the matrix?

A It is lower triangular

B It is symmetric

C It is upper triangular

D It is diagonal

The matrix is symmetric because edges go both ways between vertices.

What does a 0 in the adjacency matrix cell [i][j] mean?

A Graph is weighted

B Edge exists between vertex i and j

C Vertex i equals vertex j

D No edge between vertex i and j

Zero means no edge exists between those vertices.

Explain how an adjacency matrix represents edges in a graph and how to interpret its values.

Think of a table where rows and columns are points connected by lines.

Describe the advantages and disadvantages of using adjacency matrices for graph representation.

Consider speed versus memory use.

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