Graph Representations: Adjacency Matrix
What you'll learn: How to represent graph structures using adjacency matrices and understand their key properties.
The Core Idea
Once you've defined a graph with nodes and edges, you need a way to store it in memory that computers can work with. The adjacency matrix is one fundamental representation: a square matrix where rows and columns represent nodes, and cell values indicate whether an edge exists between them.
For a graph with n nodes, you create an n × n matrix A. If there's an edge from node i to node j, then A[i][j] = 1; otherwise, A[i][j] = 0.
Key Properties
Sparsity
Real-world graphs (social networks, molecules) are typically sparse—most nodes connect to only a few others, not everyone. This means the adjacency matrix is mostly zeros, which wastes memory. A matrix storing a million-node graph with average degree 10 would be 99.999% zeros!
Symmetry for Undirected Graphs
In undirected graphs (friendships, molecular bonds), if node i connects to node j, then j also connects to i. The adjacency matrix becomes symmetric: A[i][j] = A[j][i]. You only need to store half of it, though in practice we often keep both for simplicity.
Memory Complexity
The adjacency matrix requires O(n²) memory regardless of how many edges exist. For 10,000 nodes, that's 100 million entries—even if you only have 50,000 edges. This makes adjacency matrices impractical for large sparse graphs, but they shine for dense graphs or when you need fast edge lookups.
Analogy
Think of a conference attendance sheet where rows and columns are people's names. A checkmark at row Alice, column Bob means "Alice knows Bob." Most cells are blank (sparse), and if it's a friendship table, it's symmetric (Alice knows Bob = Bob knows Alice).
Key Takeaway: Adjacency matrices offer O(1) edge lookup but waste memory on sparse graphs with O(n²) storage, and are symmetric for undirected graphs.