Graph Representations

A graph representation encodes only one fact — which vertex pairs are connected — and the choice between a matrix and a list trades O(1) edge-lookup against compact, work-proportional storage, which is why the same traversal algorithm can be fast or slow purely based on how the graph is stored.

Recognize the pattern

• Need to repeatedly ask "does edge (u, v) exist?" or graph is dense (E close to V²) → adjacency matrix.
• Need to "iterate all neighbors of v" (BFS/DFS, Dijkstra, topological sort) or graph is sparse (E ≈ V) → adjacency list.
• Constraints show N ≤ 500 and edges roughly V² → matrix is fine.
• Constraints show N up to 10⁵ → O(N²) memory for a matrix is infeasible; must use a list.
• Weighted graph → list stores (neighbor, weight) pairs; matrix stores the weight directly in the cell instead of 1.

Brute force vs optimal

Adjacency matrix (naive for sparse graphs): allocate an N×N array, set A[i][j] = 1 for each edge (both A[i][j] and A[j][i] if undirected). Edge-exists query is O(1) — direct index. But listing v's neighbors costs O(N) — you must scan the entire row even if v has only 2 neighbors — and memory is O(N²) no matter how many edges actually exist.

Adjacency list (optimal for sparse graphs): each vertex keeps a dynamic list of its neighbors. Building costs O(V + E). Listing v's neighbors costs O(deg(v)), proportional to real work. Edge-exists degrades to O(deg(v)) linear scan (or O(1) amortized if the list is backed by a hash set instead of an array).

For E « V² the list wins on both axes — full-graph traversal becomes O(V+E) instead of O(V²). For dense graphs the two costs converge and the matrix's O(1) lookup and simplicity win.

Complexity, derived

The O(V+E) traversal bound for lists comes directly from summing degrees. For undirected graphs, ∑deg(v) = 2E (handshake lemma) — each edge is counted once from each endpoint — so visiting every vertex's list exactly once costs O(V) for the vertex loop plus O(2E) = O(E) for the edge visits, giving O(V+E), not O(V·E). For directed graphs — like the worked example below — the same argument uses out-degree instead: ∑outdeg(v) = E exactly, with no factor of 2, because each directed edge is counted once, from its source vertex only. The vertex loop is still O(V) and the total edge visits are still O(E), so the bound is O(V+E) either way — the handshake lemma just supplies the factor of 2 for undirected graphs and drops it for directed ones.

Worked example

Directed graph, 4 vertices (A=0, B=1, C=2, D=3), edges A→B, A→C, C→D, D→B, D→C.

Adjacency matrix (row = from, col = to):

Adjacency list (same graph): A → [B, C]; B → []; C → [D]; D → [B, C].

Storage check: matrix uses 16 cells regardless of edge count; list uses 4 head slots + 5 entries = 9 units — cheaper here, and the gap widens as N grows while E stays small.

Java: both representations for the worked example

import java.util.*;

public class GraphRepresentations {
    public static void main(String[] args) {
        int n = 4; // A=0, B=1, C=2, D=3
        int[][] edges = {{0,1}, {0,2}, {2,3}, {3,1}, {3,2}};

        // Adjacency matrix
        int[][] matrix = new int[n][n];
        for (int[] e : edges) matrix[e[0]][e[1]] = 1; // directed

        // Adjacency list
        List> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);

        System.out.println("Matrix row A: " + Arrays.toString(matrix[0]));
        System.out.println("List for A: " + adj.get(0));
    }
}

Pitfalls

• Forgetting to set both A[i][j] and A[j][i] for undirected graphs — breaks symmetry and silently produces a directed graph's behavior.
• Allocating an N×N matrix when N is large (e.g. 10⁵) — this is 10¹⁰ cells and will OOM or TLE on allocation alone.
• Using an adjacency list array indexed by node value when node IDs aren't 0..N-1 (e.g. strings or sparse IDs) — needs a hash map from ID to list, not a raw array.
• For weighted graphs, storing weight as a separate parallel structure instead of pairing it with the neighbor — leads to index-sync bugs when lists are mutated.
• Assuming O(1) edge lookup on an adjacency list without building a hash set — a naive list scan is O(deg(v)), which surprises people under tight TLEs.

When to use / when not

Adjacency matrix — use when the graph is dense, N is small (roughly N ≤ 1000), or you need frequent O(1) edge-existence checks (e.g. Floyd-Warshall all-pairs shortest path, which is inherently O(V³) and matrix-native). Avoid when N is large or the graph is sparse — you pay O(V²) memory for edges that mostly don't exist.

Adjacency list — use for sparse graphs, BFS/DFS, Dijkstra, topological sort, or any large-N graph. Avoid when you need frequent arbitrary edge-existence checks at scale without a backing hash set, since that degrades to O(deg(v)).

Named alternative — edge list (a flat array of (u, v[, w]) triples): more compact to build than either (O(E) to construct, no per-vertex bookkeeping) and is what Kruskal's MST algorithm wants directly since it needs edges sorted by weight, not grouped by vertex. But it's the worst for neighbor queries — O(E) scan to find v's neighbors — so it's rarely used for traversal.

Takeaways

• Adjacency matrix: O(V²) space, O(1) edge check, O(V) neighbor scan — good for dense graphs and all-pairs algorithms.
• Adjacency list: O(V+E) space and traversal, O(deg(v)) neighbor scan — the default for sparse graphs and most interview problems.
• The O(V+E) bound comes from summing vertex degrees: for undirected graphs the handshake lemma (∑deg(v) = 2E) counts each edge twice; for directed graphs ∑outdeg(v) = E counts each edge once — either way the edge-visit term collapses to O(E).
• Edge list is a third option, better for algorithms that sort/process edges globally (Kruskal's) rather than per-vertex.

Recall: Why does full-graph BFS/DFS cost O(V²) on an adjacency matrix but O(V+E) on an adjacency list, even though both visit every vertex once?

Synthesized from standard adjacency matrix/list treatments (CLRS graph representations chapter) and common interview-prep graph traversal material.