Source: CS 225 Lecture (Graph Implementations), UIUC
Difficulty: Intermediate | Prerequisites: Part 1 of these notes (Graph ADT and Edge List), 2D arrays, basic Big-O.
The edge list from Part 1 is simple but slow for queries. The adjacency matrix is the second implementation CS 225 introduces, and it solves the query-speed problem by trading space for time. Instead of scanning a list to check whether two vertices are connected, you index directly into a 2D array. This makes it ideal for dense graphs but expensive for sparse ones. Understanding this trade-off is central to choosing the right graph implementation for a given problem.
An adjacency matrix stores graph connectivity in an n-by-n 2D array, where entry (i, j) indicates whether vertices i and j are connected (and can store a pointer to the edge). areAdjacent becomes O(1), but the matrix always uses O(n^2) space regardless of how many edges exist, and incidentEdges requires scanning an entire row, costing O(n).
Adjacency matrix
An n x n 2D array where rows and columns correspond to vertices. Entry (i, j) stores whether an edge exists between vertex i and vertex j. Think of it as a spreadsheet where every cell answers "are these two connected?"
Dense graph
A graph where the number of edges m is close to the maximum possible (n^2 for directed, n(n-1)/2 for undirected). In simple terms, most vertices are connected to most other vertices. The adjacency matrix is well suited to dense graphs.
Sparse graph
A graph where the number of edges m is much smaller than n^2. Most vertices have relatively few connections. The adjacency matrix wastes a lot of space on sparse graphs because the matrix is mostly zeros.
Symmetric matrix
In an undirected graph, the adjacency matrix is symmetric: entry (i, j) equals entry (j, i). This means you only need to fill the upper triangle (or lower triangle) plus the diagonal; the other half mirrors it.
Edge-to-matrix pointer
In the lecture's implementation, matrix cells do not just store 0 or 1. They store a pointer (or reference) back to the edge object in the edge collection. This lets you go from "yes, these are adjacent" to the full edge data in O(1).
The adjacency matrix adds a second data structure on top of the vertex and edge collections from the edge list. It is an n x n array (where n is the number of vertices), and each cell (i, j) either stores a null/zero (no edge) or a pointer to the edge connecting vertex i and vertex j.
For the lecture's running example with vertices {0, 1, 2, 3} and edges {(0,1,a), (1,2,b), (0,2,c), (2,3,d)}, the matrix looks like this:
0 | 1 | 2 | 3 | |
|---|---|---|---|---|
0 | - | 1 | 1 | 0 |
1 | - | 1 | 0 | |
2 | - | 1 | ||
3 | - |
The diagonal is marked "-" (a vertex has no edge to itself in a simple graph). For an undirected graph the matrix is symmetric, so the lower triangle mirrors the upper.
In the full implementation, the 1s are replaced by pointers back to the edge list entries, so you can retrieve the edge's label or weight in O(1) once you know the cell.
areAdjacent(v1, v2): Look up matrix[v1][v2]. If it is non-null, return true. O(1). This is the adjacency matrix's headline advantage.
incidentEdges(v): Scan the entire row (or column) for vertex v, collecting every non-null entry. O(n), because there are n columns to check.
insertEdge(v1, v2, key): Add the edge to the edge collection, then set matrix[v1][v2] (and matrix[v2][v1] for undirected) to point to it. O(1).
removeEdge(v1, v2): Set matrix[v1][v2] (and matrix[v2][v1]) to null, then remove the edge from the edge collection. O(1).
insertVertex: Add to the vertex collection. If the matrix is full, you must grow the matrix (allocate a new, larger 2D array and copy). Amortised O(1) with a growable array, but the resize itself is O(n^2).
removeVertex: Remove from the vertex collection, scan the vertex's row and column to remove all incident edges, then shrink or reorganise the matrix. O(n).
The adjacency matrix shines when you need fast adjacency checks and the graph is dense (m is close to n^2). For a sparse graph, most of the n^2 cells are empty, so the space cost is hard to justify. In that scenario, an adjacency list is usually the better choice.
Let n = number of vertices, m = number of edges.
Operation | Edge List | Adjacency Matrix |
|---|---|---|
Space | O(n + m) | O(n^2) |
insertVertex | O(1) | O(1) amortised; O(n^2) on resize |
removeVertex | O(m) | O(n) |
insertEdge | O(1) | O(1) |
removeEdge | O(m) | O(1) |
incidentEdges | O(m) | O(n) |
areAdjacent | O(m) | O(1) |
The adjacency matrix wins on areAdjacent (O(1) vs. O(m)), removeEdge (O(1) vs. O(m)), and incidentEdges (O(n) vs. O(m), which is better when the graph is dense and m approaches n^2). It loses on space (O(n^2) vs. O(n + m)).
For sparse graphs where m is much less than n^2, the edge list (or better, an adjacency list) uses far less memory.
Students often think the adjacency matrix stores only 0s and 1s. In the CS 225 implementation, cells store pointers to edge objects, not just booleans. The 0/1 view is a simplification.
Students sometimes forget that the adjacency matrix is symmetric for undirected graphs. If you set matrix[0][2] you must also set matrix[2][0]. Forgetting this breaks areAdjacent when called in the "wrong" order.
A common mistake is to say incidentEdges on an adjacency matrix is O(m). It is O(n): you scan one row of n columns, not the whole edge list.
Students often assume the adjacency matrix is always better than the edge list because areAdjacent is faster. It is better only for query-heavy workloads. For sparse graphs with few queries, the O(n^2) space cost makes it a poor choice.
⚠️ The side-by-side complexity comparison table (edge list vs. adjacency matrix) is one of the most commonly tested items in CS 225 graph exams. Memorise it.
⚠️ Be able to fill in an adjacency matrix from a given graph diagram and vice versa. The lecture walks through this for the (0,1,2,3) example graph.
⚠️ Expect a question asking you to choose the best graph implementation for a described scenario. The answer depends on whether the graph is sparse or dense and whether the workload is query-heavy or modification-heavy.
⚠️ Know that the adjacency matrix cells point back to the edge list entries. The matrix is an overlay that provides fast lookup; it does not replace the edge collection.
True or False: areAdjacent on an adjacency matrix is O(n).
Fill in the blank: The space complexity of an adjacency matrix is O(______).
True or False: In an undirected graph, the adjacency matrix is symmetric.
Fill in the blank: incidentEdges on an adjacency matrix scans one ______ of the matrix, costing O(______).
True or False: The adjacency matrix is the best choice for a sparse graph with 1,000 vertices and 50 edges.
Answers: 1. False (it is O(1)). 2. n^2. 3. True. 4. row, n. 5. False (O(n^2) = 1,000,000 cells for 50 edges is very wasteful).
Q: Draw the adjacency matrix for an undirected graph with vertices {A, B, C} and edges {(A,B), (B,C)}.
A: Using 0-indexing where A=0, B=1, C=2: row 0 = [-, 1, 0], row 1 = [1, -, 1], row 2 = [0, 1, -]. The matrix is symmetric.
Q: A social network has 10,000 users but the average user has only 150 friends. Would you use an adjacency matrix or an adjacency list? Justify your answer.
A: Adjacency list. The graph is very sparse (about 750,000 edges vs. a 100,000,000-cell matrix). The adjacency matrix would waste the vast majority of its space on zeros.
Q: What is the runtime of removeEdge(v1, v2) on an adjacency matrix, and why is it faster than on an edge list?
A: O(1). You go directly to matrix[v1][v2] and set it to null (and matrix[v2][v1] for undirected). On an edge list, you must scan up to m edges to find the one to remove.
Q: Explain why incidentEdges on an adjacency matrix is O(n) rather than O(m).
A: You scan the vertex's row in the matrix, which has exactly n columns. Each column check is O(1). The total is O(n), regardless of how many edges exist in the whole graph.
Q: A graph has n = 100 vertices and m = 4,900 edges (nearly complete). Compare the space cost of an edge list and an adjacency matrix.
A: Edge list: O(n + m) = O(100 + 4,900) = O(5,000). Adjacency matrix: O(n^2) = O(10,000). The adjacency matrix uses about twice the space, but provides O(1) adjacency checks, which is a worthwhile trade-off for a near-complete graph.
The adjacency matrix is one of three main graph implementations in CS 225. The third, the adjacency list, combines ideas from both: it keeps per-vertex linked lists of neighbours, giving O(deg(v)) for incidentEdges and O(deg(v)) for areAdjacent.
Graph traversal algorithms (BFS, DFS) iterate over a vertex's neighbours. The cost of that step depends directly on whether you are using an edge list (O(m)), adjacency matrix (O(n)), or adjacency list (O(deg(v))), so these implementation details carry forward into every graph algorithm's runtime analysis.
The adjacency matrix also appears outside CS 225 in linear algebra and network analysis, where matrix operations (multiplication, eigenvalues) reveal properties of the graph such as connectivity and centrality.
Adjacency matrix, adjacency matrix implementation, graph matrix, 2D array graph, graph representation, dense graph, sparse graph, symmetric matrix, areAdjacent O(1), incidentEdges O(n), graph space complexity, edge list vs adjacency matrix, graph implementation comparison, CS 225, data structures, UIUC, graph storage, graph ADT, adjacency check, vertex-indexed array