Adjacency Matrix Representation in DSA Java - 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 from vertex i to vertex j.

beginner

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

You represent no edge by putting 0 in the matrix cell corresponding to those two vertices.

intermediate

What value is stored in the adjacency matrix for weighted graphs when there is an edge?

The weight of the edge is stored in the matrix cell corresponding to the two vertices connected by that edge.

beginner

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

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

intermediate

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

It uses more memory than needed because it stores V x V cells even if there are few edges, leading to wasted space.

In an adjacency matrix, what does a 1 typically represent in an unweighted graph?

A There is an edge between two vertices

B There is no edge between two vertices

C The weight of the edge

D The number of vertices

A 1 indicates presence of an edge between the two vertices in an unweighted graph.

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

A O(V)

B O(V^2)

C O(E)

D O(1)

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

Which graph type is adjacency matrix less efficient for?

A Dense graphs

B Sparse graphs

C Complete graphs

D Directed graphs

Adjacency matrix wastes space for sparse graphs because most cells are zero.

What does the diagonal of an adjacency matrix represent in a simple graph?

A Number of vertices

B Edges between different vertices

C Edges from a vertex to itself

D Weights of edges

Diagonal cells represent self-loops, edges from a vertex to itself.

How do you represent a directed edge from vertex i to vertex j in adjacency matrix?

A Set matrix[i][j] to 1 or weight

B Set matrix[j][i] to 1 or weight

C Set matrix[i][i] to 1

D Set matrix[j][j] to 1

For directed graphs, matrix[i][j] shows edge from i to j.

Explain how an adjacency matrix represents edges in both weighted and unweighted graphs.

Think about what each cell in the matrix means.

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

Consider speed and memory usage.

Practice

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

easy

A. A 2D array showing edges between nodes

B. A list of nodes in the graph

C. A sequence of visited nodes

D. A stack used for graph traversal

Solution

1. Step 1: Understand adjacency matrix concept

   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 an edge exists between two nodes (1 for edge, 0 for no edge).

3. Final Answer:

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

4. Quick Check:

   Adjacency matrix = 2D array of edges [OK]

Hint: Adjacency matrix is always a 2D array showing connections [OK]

Common Mistakes:

• Confusing adjacency matrix with adjacency list
• Thinking it stores node values instead of edges
• Mixing it up with traversal order

2. Which of the following is the correct way to declare an adjacency matrix for a graph with 4 nodes in Java?

easy

A. int[] matrix = new int[4][4];

B. int matrix = new int[4];

C. int[][] matrix = new int[4][4];

D. int[][] matrix = new int[4];

Solution

1. Step 1: Recall Java 2D array declaration syntax

   In Java, a 2D array is declared as type[][] name = new type[rows][columns];

2. Step 2: Match with graph nodes count

   For 4 nodes, we need a 4x4 matrix, so new int[4][4] is correct.

3. Final Answer:

   int[][] matrix = new int[4][4]; -> Option C

4. Quick Check:

   2D array for 4 nodes = new int[4][4] [OK]

Hint: 2D array syntax: type[][] name = new type[size][size]; [OK]

Common Mistakes:

• Using single brackets for 2D array
• Declaring 1D array instead of 2D
• Incorrect array initialization syntax

3. Given the following adjacency matrix for a graph with 3 nodes:

int[][] matrix = {
  {0, 1, 0},
  {1, 0, 1},
  {0, 1, 0}
};
What is the output of the code snippet?
for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; j++) {
    if (matrix[i][j] == 1) {
      System.out.print(i + "->" + j + " ");
    }
  }
}

medium

A. 0->2 2->0

B. 0->0 1->1 2->2

C. 1->0 2->1

D. 0->1 1->0 1->2 2->1

Solution

1. Step 1: Analyze the matrix values

   matrix[0][1] = 1, matrix[1][0] = 1, matrix[1][2] = 1, matrix[2][1] = 1; others are 0.

2. Step 2: Trace the nested loops and print statements

   For each 1, print "i->j ": 0->1, 1->0, 1->2, 2->1.

3. Final Answer:

   0->1 1->0 1->2 2->1 -> Option D

4. Quick Check:

   Edges printed where matrix[i][j] = 1 [OK]

Hint: Print edges where matrix cell is 1 [OK]

Common Mistakes:

• Printing zeros as edges
• Mixing i and j indices
• Skipping symmetric edges

4. Identify the error in the following code snippet that tries to create an adjacency matrix for 3 nodes:

int[][] matrix = new int[3];
matrix[0][1] = 1;

medium

A. Index out of bounds error at matrix[0][1]

B. 2D array declared incorrectly with single dimension

C. Matrix values cannot be assigned directly

D. Missing import statement for arrays

Solution

1. Step 1: Check array declaration syntax

   int[][] matrix = new int[3]; declares a 1D array of int arrays but does not initialize inner arrays.

2. Step 2: Understand why matrix[0][1] causes error

   Inner arrays are null, so accessing matrix[0][1] causes NullPointerException or compile error.

3. Final Answer:

   2D array declared incorrectly with single dimension -> Option B

4. Quick Check:

   2D array needs both dimensions declared [OK]

Hint: Declare both dimensions for 2D arrays: new int[size][size] [OK]

Common Mistakes:

• Declaring only one dimension for 2D array
• Not initializing inner arrays
• Confusing array types

5. You have a directed graph with 4 nodes and edges: 0->1, 0->2, 1->2, 2->3. Which adjacency matrix correctly represents this graph?

hard

A. [[0,1,1,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]]

B. [[0,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,0,0]]

C. [[0,0,1,0],[0,0,0,1],[1,0,0,0],[0,0,0,0]]

D. [[0,1,1,1],[0,0,1,0],[0,0,0,0],[0,0,0,0]]

Solution

1. Step 1: Map edges to matrix positions

   Edges: 0->1 means matrix[0][1]=1, 0->2 means matrix[0][2]=1, 1->2 means matrix[1][2]=1, 2->3 means matrix[2][3]=1.

2. Step 2: Check each option for these values

   [[0,1,1,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]] matches exactly these edges with 1s in correct places and 0s elsewhere.

3. Final Answer:

   [[0,1,1,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]] -> Option A

4. Quick Check:

   Edges mapped as 1s in matrix [OK]

Hint: Mark 1 for each edge from row to column [OK]

Common Mistakes:

• Confusing directed edges with undirected
• Placing 1s symmetrically for directed graph
• Missing edges in matrix