Adjacency Matrix Representation in DSA Java - 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 with 3 nodes?

DSA Java

int[][] matrix = new int[3][3];
matrix[0][1] = 1;
matrix[1][0] = 1;
matrix[1][2] = 1;
matrix[2][1] = 1;
matrix[2][0] = 1;
matrix[0][2] = 1;
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        System.out.print(matrix[i][j] + " ");
    }
    System.out.println();
}

A [[0,0,0],[0,0,0],[0,0,0]]

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

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

D [[1,1,1],[1,1,1],[1,1,1]]

💡 Hint

Remember that for an undirected graph, edges are symmetric in the matrix.

The adjacency matrix is symmetric because the graph is undirected. Edges between nodes 0-1, 1-2, and 2-0 set the corresponding entries to 1 in both directions.

❓ Predict Output

intermediate

Output of adjacency matrix for directed graph

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

DSA Java

int[][] matrix = new int[3][3];
matrix[0][1] = 1;
matrix[1][2] = 1;
matrix[2][0] = 1;
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        System.out.print(matrix[i][j] + " ");
    }
    System.out.println();
}

A [[0,0,0],[0,0,0],[0,0,0]]

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

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

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

💡 Hint

Directed edges only set one direction in the matrix.

Each directed edge sets matrix[from][to] = 1 only. So 0->1 sets matrix[0][1] = 1, and so on.

🔧 Debug

advanced

Identify the error in adjacency matrix initialization

What error will this code cause when creating an adjacency matrix for 3 nodes and adding an edge from node 0 to node 3?

DSA Java

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

A NullPointerException

B ArrayIndexOutOfBoundsException

C SyntaxError

D No error, runs fine

💡 Hint

Check the valid indices for a 3x3 matrix.

Index 3 is out of bounds for an array of size 3 (valid indices are 0,1,2). This causes ArrayIndexOutOfBoundsException.

🧠 Conceptual

advanced

Memory usage comparison of adjacency matrix vs adjacency list

For a graph with 1000 nodes and 10 edges, which statement about memory usage is true?

A Adjacency matrix uses more memory because it stores 1,000,000 entries regardless of edges.

B Both use the same memory since they represent the same graph.

C Adjacency list uses more memory because it stores all edges explicitly.

D Adjacency matrix uses less memory because it uses a fixed size.

💡 Hint

Think about how adjacency matrix size depends on nodes, not edges.

An adjacency matrix always uses memory proportional to nodes squared, while adjacency list memory depends on edges. For sparse graphs, adjacency list is more memory efficient.

🚀 Application

expert

Find if a graph is complete using adjacency matrix

Given an adjacency matrix of size n x n for an undirected graph, which code snippet correctly checks if the graph is complete (every pair of distinct nodes connected)?

A

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    if (i != j && matrix[i][j] == 0) return false;
  }
}
return true;

B

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    if (matrix[i][j] == 1) return false;
  }
}
return true;

C

for (int i = 0; i < n; i++) {
  if (matrix[i][i] == 1) return false;
}
return true;

D

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    if (i == j && matrix[i][j] == 1) return false;
  }
}
return true;

💡 Hint

A complete graph has edges between every pair of different nodes.

Option A checks all pairs of distinct nodes and returns false if any pair is not connected (0). This correctly identifies completeness.

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