Graph representations
Overview
A graph is conceptually a set of vertices (nodes) and edges (connections). The two primary ways to represent this in code are the Adjacency List and the Adjacency Matrix. An adjacency list maps each vertex to a list of its immediate neighbors. It takes `O(V+E)` space, scanning neighbors takes `O(deg(v))` time, and checking a specific edge takes `O(deg(v))` time. An adjacency matrix uses a 2D array of size `V x V`, where a cell `[u][v]` is 1 if an edge exists, and 0 otherwise. It takes `O(V^2)` space and checks specific edges in `O(1)` time. Whether a graph is directed or undirected matters for how you build these. An undirected edge between `A` and `B` is stored twice (as `A->B` and `B->A`). A directed edge is stored only once. Graphs can also have self-loops (an edge from a node to itself) or multi-edges (multiple edges between the same two nodes).
The adjacency list is the default because real-world graphs are sparse (edges `E` are much less than `V^2`). A matrix burns `O(V^2)` memory to store mostly zeros. The matrix wins only on very dense graphs or when you absolutely need `O(1)` edge-existence queries.
Where used: Social network follower connections (Adjacency List), Dense machine learning similarity matrices (Adjacency Matrix)
Why learn this
- The primary challenge in computational graph theory is translating a conceptual network into a memory-efficient digital structure.
- The choice of representation dictates the time and space complexity lower bounds for all subsequent operations.
Common mistakes
- Using an adjacency matrix for a sparse graph: Allocating a V by V matrix for a sparse graph wastes massive memory (`O(V^2)`) and forces `O(V^2)` traversal time since algorithms must scan every possible connection, mostly hitting zeros.
- Forgetting to add the reverse edge for undirected graphs: In an undirected graph, an edge between A and B must be stored as both `A->B` and `B->A` in the adjacency list. Omitting one breaks traversals and connectivity.
Recall questions
- What is the space complexity of an adjacency list versus an adjacency matrix?
- Why is the adjacency list the default representation for most graphs?
- How is an undirected edge stored in an adjacency list?
Understanding checks
Based on the adjacency list above, how many undirected edges are in the graph?
2
The edges are 0-1 and 1-2. Because it's undirected, each edge appears twice in the list (0->1, 1->0 and 1->2, 2->1), for a total of 4 entries, representing 2 actual undirected edges.
A candidate says: 'The adjacency matrix is just better because checking if an edge exists is O(1).' What is the flaw in this reasoning?
It ignores the severe space complexity penalty and the cost of neighbor iteration. Standard traversals like BFS and DFS need to visit all neighbors, taking O(V^2) total time with a matrix but only O(V+E) with a list.
Matrix edge lookup is O(1), but memory is O(V^2). Unless the graph is extremely dense or you exclusively need existence checks, the list is superior.
Practice tasks
Convert directed edges to an undirected adjacency list
Given this function that builds a DIRECTED adjacency list, modify it so it builds an UNDIRECTED adjacency list.
Continue learning
Previous: Iteration & Traversal
Next: Weighted vs unweighted
Next: BFS on graphs
Next: DFS on Graphs