Adjacency Matrix vs. Adjacency List
When designing graph-based algorithms, selecting the appropriate representation in memory is critical for optimizing both time and space complexity. Here is a direct comparison between the two primary representation models.
Comparison Table
| Operations | Adjacency Matrix | Adjacency List |
|---|---|---|
| Storage Space | This representation makes use of a $V \times V$ matrix, so the space required in the worst case is $O(\vert V \vert^2)$. | For every vertex, we store only its neighbors. The overall space complexity is $O(\vert V \vert + \vert E \vert)$. |
| Adding a Vertex | To add a vertex, the matrix must be resized to $(\vert V \vert + 1) \times (\vert V \vert + 1)$. This requires copying the whole matrix, resulting in $O(\vert V \vert^2)$ complexity. | In array/map implementations, a new vertex can be added directly, taking $O(1)$ time. |
| Adding an Edge | To add an edge from vertex $i$ to $j$, we set $matrix[i][j] = 1$, which takes constant $O(1)$ time. | We insert the edge at the front or rear of the vertex's list, taking $O(1)$ time. |
| Removing a Vertex | The matrix size must be decreased back to $\vert V \vert^2$. Re-allocating and copying the entire matrix takes $O(\vert V \vert^2)$ time. | We must remove the vertex from our list/map and traverse all other lists to clean up any references to it, taking $O(\vert V \vert + \vert E \vert)$ time. |
| Removing an Edge | To remove an edge, we reset $matrix[i][j] = 0$, which takes $O(1)$ time. | We must search the list of neighbors for that vertex. This takes time proportional to the number of neighbors, which is $O(\vert V \vert)$ in the worst case (or up to $O(\vert E \vert)$ to search all edges). |
Querying Edge Existence (u -> v) | Checking if an edge exists is as simple as accessing $matrix[u][v]$, which takes $O(1)$ time. | We must scan the neighbor list of vertex $u$, which takes $O(\vert V \vert)$ in the worst case. |
Design Guidelines: When to use which?
Choose Adjacency Matrix if:
- Dense Graph: The graph is dense (i.e., the number of edges $\vert E \vert$ is close to $\vert V \vert^2$).
- Frequent Edge Lookups: You need to frequently query whether an edge exists between two vertices in $O(1)$ time.
- Small Graphs: The number of vertices is relatively small, making the space overhead negligible.
Choose Adjacency List if:
- Sparse Graph: The graph is sparse (i.e., $\vert E \vert \ll \vert V \vert^2$). This is the case for most real-world graphs (like road networks, social networks, etc.).
- Neighbor Iteration: The algorithm requires visiting or processing all neighbors of a vertex (e.g., Breadth-First Search or Depth-First Search).
- Vertex Additions: You need to dynamically insert new vertices frequently.