Graph Adjacency Matrix
Overview
An Adjacency Matrix is the second primary way to represent a graph. Instead of lists, it uses a 2D Array (a grid) of size V x V (Vertices by Vertices).
If there is an edge connecting Node 0 and Node 1, we set matrix[0][1] = 1. If there is no edge, it remains 0. For a weighted graph, we store the weight of the edge instead of a simple 1.
The massive advantage of a Matrix is O(1) edge lookup. If you want to know if Node 4 and Node 8 are connected, you simply check matrix[4][8].
However, the fatal flaw of the Matrix is Space Complexity. A graph with 10,000 vertices requires a 10,000 x 10,000 array, allocating 100 million integers (400MB of RAM)! Even if there are only 5 edges in the entire graph, it still uses 400MB. Therefore, Matrices are only used for Dense Graphs (where almost every node is connected to every other node) or very small graphs.
Syntax
public class GraphMatrix {
private int[][] matrix;
private int numVertices;
public GraphMatrix(int numVertices) {
this.numVertices = numVertices;
// In Java, integer arrays default to 0 (no edge)
matrix = new int[numVertices][numVertices];
}
// Add an undirected edge
public void addEdge(int i, int j) {
matrix[i][j] = 1;
matrix[j][i] = 1; // Undirected means mirrored across the diagonal
}
// Remove an edge
public void removeEdge(int i, int j) {
matrix[i][j] = 0;
matrix[j][i] = 0;
}
// O(1) Check if connected
public boolean isConnected(int i, int j) {
return matrix[i][j] == 1;
}
// Print the matrix
public void print() {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}Common Pitfalls
- Running out of memory (
OutOfMemoryError). Never use an Adjacency Matrix in a coding interview if the number of nodesNis greater than 1,000 unless specifically instructed to. $10^5$ nodes requires a $10^{10}$ size array, which will instantly crash your program. - Iterating over neighbors is extremely slow. To find all neighbors of Node 0, you must iterate through the entire row
matrix[0], checking every single node from 1 to N to see if it equals 1. This makes traversal algorithms like BFS/DFS run in O(V^2) time instead of O(V + E). - Handling node IDs. A matrix requires node IDs to be sequential integers from
0toV-1. If your nodes are Strings ('New York', 'London'), you must create an entirely separateHashMap<String, Integer>just to map the names to valid array indices.
Interview Questions
All three operations are strictly O(1) time complexity. You are just accessing and modifying a 2D array by index.
It is 'Symmetric' across its main diagonal. The value at matrix[i][j] will always exactly match the value at matrix[j][i].
Real-World Example
Flight routing maps between a small network of major airports. If you only have 50 major airports, a 50x50 matrix is tiny. A matrix perfectly models a dense network where almost every airport has direct flights to every other airport. The matrix cells can hold the flight cost or distance (Weighted Graph).
// A weighted adjacency matrix
int numAirports = 5;
int[][] flightCosts = new int[numAirports][numAirports];
// Initialize all routes to 'Infinity' (No route exists)
for(int[] row : flightCosts) {
Arrays.fill(row, Integer.MAX_VALUE);
}
// JFK (0) to LAX (1) costs $450
flightCosts[0][1] = 450;
flightCosts[1][0] = 450;Check Your Knowledge
Test your understanding of Graph Adjacency Matrix with these quick questions.