Adjacency Matrix Representation in DSA Java - Execution Trace

Concept Flow - Adjacency Matrix Representation

Start

↓

Create NxN matrix

↓

Initialize all cells to 0

↓

For each edge (u,v)

↓

Set matrix[u

↓

If undirected, set matrix[v

↓

Repeat for all edges

↓

Adjacency matrix ready

Build a square matrix where each cell shows if an edge exists between two nodes.

Execution Sample

DSA Java

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

Create a 4-node graph adjacency matrix and mark edges between nodes.

Execution Table

Step	Operation	Matrix State	Pointer Changes	Visual State
1	Create 4x4 matrix initialized to 0	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	matrix created	Empty 4x4 matrix with all zeros
2	Add edge 0->1	[[0,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	matrix[0][1] = 1	Mark edge from node 0 to 1
3	Add edge 1->2	[[0,1,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	matrix[1][2] = 1	Mark edge from node 1 to 2
4	Add edge 2->3	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]]	matrix[2][3] = 1	Mark edge from node 2 to 3
5	Add edge 3->0	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	matrix[3][0] = 1	Mark edge from node 3 to 0
6	End	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	No changes	Final adjacency matrix representing graph edges

💡 All edges added, matrix fully represents graph connections

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
matrix	null	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]	[[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]

Key Moments - 3 Insights

Why do we initialize the matrix with zeros before adding edges?

Because zeros mean no edges between nodes. This is shown in execution_table step 1 where the matrix starts empty.

Why does matrix[0][1] = 1 represent an edge from node 0 to node 1?

Because the matrix row is the source node and column is the destination. Step 2 in execution_table shows this clearly.

What if the graph is undirected? How does the matrix change?

We set both matrix[u][v] and matrix[v][u] to 1 for each edge. This is not shown here but would mean symmetric entries.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the matrix value at position [1][2]?

A 0

B 2

C 1

D -1

💡 Hint

Check the 'Matrix State' column at step 3 in execution_table

At which step does the edge from node 3 to node 0 get added?

A Step 4

B Step 5

C Step 2

D Step 6

💡 Hint

Look for matrix[3][0] = 1 in the 'Pointer Changes' column in execution_table

If the graph was undirected, how would the matrix change after adding edge 0->1?

A matrix[0][1] = 1 and matrix[1][0] = 1

B matrix[1][0] = 1 only

C Only matrix[0][1] = 1

D No changes to matrix

💡 Hint

Recall undirected edges require symmetric entries in adjacency matrix

Concept Snapshot

Adjacency Matrix Representation:
- Use NxN matrix for N nodes
- matrix[i][j] = 1 means edge from i to j
- Initialize all cells to 0 (no edges)
- For undirected graphs, matrix[i][j] = matrix[j][i] = 1
- Easy to check edge existence in O(1) time

Full Transcript

Adjacency Matrix Representation uses a square matrix to show connections between nodes. We start by creating an NxN matrix filled with zeros, meaning no edges. Then for each edge from node u to node v, we set matrix[u][v] to 1. If the graph is undirected, we also set matrix[v][u] to 1 to show the two-way connection. This method makes it quick to check if an edge exists between any two nodes by looking at the matrix cell. The example code creates a 4-node graph and adds edges step by step, updating the matrix accordingly. The final matrix clearly shows all connections.

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