Adjacency Matrix: Structure and Memory
What You'll Learn
You'll learn how to represent graphs using a 2D array where each entry tells you whether an edge exists between two vertices.
The Core Idea
An adjacency matrix is one of the most straightforward ways to store a graph in memory. Imagine you have a graph with n vertices numbered 0 through n-1. You create a 2D array (a matrix) of size n × n. Each cell at position (i, j) answers the question: "Is there an edge from vertex i to vertex j?"
For an unweighted graph, the matrix stores Boolean-like values:
matrix[i][j] = 1(ortrue) means an edge exists from vertexito vertexjmatrix[i][j] = 0(orfalse) means no edge exists
For a weighted graph, instead of just 1 or 0, you store the edge weight at matrix[i][j], and use a special value (like infinity or -1) to indicate "no edge."
Undirected vs Directed
In an undirected graph, if there's an edge between vertices i and j, both matrix[i][j] and matrix[j][i] are set (the matrix is symmetric). In a directed graph, only the appropriate direction is marked.
Memory Footprint
The adjacency matrix always uses O(n²) space, regardless of how many edges actually exist. This makes it memory-intensive for sparse graphs (graphs with few edges) but efficient for dense graphs where most vertex pairs are connected.
Key Takeaway: An adjacency matrix uses a 2D array of size n×n to represent a graph, where each cell indicates edge presence or weight, consuming O(n²) memory regardless of edge count.