Adjacency Matrix Representation of Graphs
Learn how to represent a graph as an adjacency matrix. Understand space complexity, edge lookup time, and when a matrix is more efficient than an adjacency list.
Detailed Explanation
Adjacency Matrix
An adjacency matrix is a 2D array (or table) where the entry at row i, column j indicates whether there is an edge from node i to node j, and optionally stores its weight.
Structure
For a graph with V nodes, the matrix is V × V:
A B C D
A [ 0 1 1 0 ]
B [ 1 0 0 1 ]
C [ 1 0 0 1 ]
D [ 0 1 1 0 ]
- Undirected graph: The matrix is symmetric (M[i][j] = M[j][i])
- Directed graph: The matrix may be asymmetric
- Weighted graph: Store the weight instead of 1; use 0 or ∞ for non-edges
Time Complexity
| Operation | Time |
|---|---|
| Check if edge exists | O(1) |
| Add/remove edge | O(1) |
| Find all neighbors | O(V) |
| Space | O(V²) |
Advantages
- Constant-time edge lookup — Check M[i][j] directly
- Simple implementation — Just a 2D array
- Matrix operations — Powers of the adjacency matrix count paths of length k
Disadvantages
- O(V²) space even for sparse graphs (most entries may be zero)
- O(V) to iterate neighbors — Must scan an entire row
When to Use
Adjacency matrices work best for dense graphs where E is close to V², or when you need frequent O(1) edge existence checks. For sparse graphs, an adjacency list is typically more efficient.
Use Case
Adjacency matrices are used in mathematical graph analysis, where matrix multiplication and eigenvalue computations reveal structural properties. They are common in dense network simulations, image processing (pixel adjacency), and in algorithms like Floyd-Warshall that systematically examine all node pairs.