Topic 61 of 78
Graph Adjacency Matrix
Overview
An Adjacency Matrix is a 2D boolean (or integer) array used to represent a Graph. If the array is `matrix[V][V]`, a value of `1` or `true` at `matrix[row][col]` means there is an edge connecting Node `row` to Node `col`. While checking if an edge exists is an instant O(1) operation, an Adjacency Matrix requires massive O(V^2) memory. It is generally only used for 'dense' graphs where almost every node is connected to every other node.
Syntax
`hasEdge` is blazing fast O(1), but memory scales quadratically. A graph with 10,000 nodes requires a 10,000 x 10,000 array (100 million integers!).
Adjacency Matrix
java
public class MatrixGraph {
private int[][] matrix;
private int numVertices;
public MatrixGraph(int numVertices) {
this.numVertices = numVertices;
// Initializes with all 0s by default
matrix = new int[numVertices][numVertices];
}
public void addEdge(int source, int dest, int weight) {
matrix[source][dest] = weight;
// If undirected: matrix[dest][source] = weight;
}
public boolean hasEdge(int source, int dest) {
return matrix[source][dest] != 0;
}
}Common Pitfalls
- O(V^2) Memory limits. Creating `new int[100000][100000]` will instantly cause an OutOfMemoryError in Java.
- Iterating over all edges takes O(V^2) time, even if the graph only has 3 edges.
Interview Tips
- Use an Adjacency Matrix ONLY if the graph is very dense or if the number of vertices is very small (e.g., V < 1000).
Real-World Example
Flight routing algorithms that need to instantly check the exact cost between two major airport hubs, or pixel connectivity in image processing.
example
java
// Instantly get the price of a direct flight
int price = flightMatrix[airportJFK][airportLAX];
if (price == 0) {
System.out.println("No direct flight available.");
}