Adjacency Matrix Representation in DSA Java

Mental Model

We use a square grid to show which nodes connect to which in a graph. Each cell says if two nodes have a link.

Analogy: Think of a friendship chart in a classroom where each student has a row and a column. A mark in the grid means those two students are friends.

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Dry Run Walkthrough

Input: Graph with 3 nodes: edges between 0-1 and 1-2

Goal: Show the adjacency matrix that marks connections between nodes

Step 1: Create a 3x3 matrix filled with zeros

   0 1 2
0 [0 0 0]
1 [0 0 0]
2 [0 0 0]

Why: Start with no connections marked

Step 2: Mark connection between node 0 and 1

   0 1 2
0 [0 1 0]
1 [1 0 0]
2 [0 0 0]

Why: Set matrix[0][1] and matrix[1][0] to 1 to show edge

Step 3: Mark connection between node 1 and 2

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Why: Set matrix[1][2] and matrix[2][1] to 1 to show edge

Result:

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Annotated Code

DSA Java

public class Graph {
    private int[][] adjacencyMatrix;
    private int numVertices;

    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyMatrix = new int[numVertices][numVertices];
    }

    public void addEdge(int i, int j) {
        // Mark edge from i to j
        adjacencyMatrix[i][j] = 1;
        // Mark edge from j to i for undirected graph
        adjacencyMatrix[j][i] = 1;
    }

    public void printMatrix() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(3);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.printMatrix();
    }
}

adjacencyMatrix = new int[numVertices][numVertices];

Initialize matrix with zeros for no edges

adjacencyMatrix[i][j] = 1;

Mark edge from node i to node j

adjacencyMatrix[j][i] = 1;

Mark edge from node j to node i for undirected graph

System.out.print(adjacencyMatrix[i][j] + " ");

Print each cell in the matrix row

Output

0 1 0 

1 0 1 

0 1 0 

Complexity Analysis

Time: O(V^2) because we create and print a matrix of size V by V where V is number of vertices

Space: O(V^2) because we store a matrix with V rows and V columns

vs Alternative: Compared to adjacency lists which use O(V + E) space, adjacency matrix uses more space but allows quick edge checks

Edge Cases

Graph with zero nodes

Creates an empty matrix with no rows or columns

DSA Java

adjacencyMatrix = new int[numVertices][numVertices];

Graph with one node and no edges

Matrix is 1x1 with zero indicating no self-loop

DSA Java

adjacencyMatrix = new int[numVertices][numVertices];

Adding edge with invalid node index

Throws ArrayIndexOutOfBoundsException (not handled in code)

DSA Java

adjacencyMatrix[i][j] = 1;

When to Use This Pattern

When you need to quickly check if two nodes are connected and the graph is small or dense, use adjacency matrix representation because it gives O(1) edge lookup.

Common Mistakes

Mistake: Forgetting to mark both adjacencyMatrix[i][j] and adjacencyMatrix[j][i] in undirected graphs
Fix: Always set both positions to 1 to keep the matrix symmetric

Mistake: Using adjacency matrix for very large sparse graphs causing high memory use
Fix: Use adjacency list instead for large sparse graphs

Summary

It stores graph connections in a 2D grid where each cell shows if two nodes are linked.

Use it when the graph is small or you need fast checks if nodes connect.

Remember the matrix is square and symmetric for undirected graphs, marking both directions.

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