Quick Overview
An adjacency matrix answers "is there an edge?" in `O(1)` but costs `O(V^2)` memory. A list flips the trade: `O(V + E)` space, but checking one edge means scanning a neighbour list.
A Graph G = (V, E) consists of a set of vertices (V) connected by edges (E). Graphs can be directed (one-way streets) or undirected (two-way friendships), and weighted or unweighted.
Graph: (0) ───── (1)
│ /
│ /
(2) ── (3)
Adjacency List (Map / Array of Lists):
0: [ 1, 2 ]
1: [ 0, 3 ]
2: [ 0, 3 ]
3: [ 1, 2 ]
Adjacency Matrix (2D Grid):
0 1 2 3
0 [ 0, 1, 1, 0 ]
1 [ 1, 0, 0, 1 ]
2 [ 1, 0, 0, 1 ]
3 [ 0, 1, 1, 0 ]
function buildGraph(numVertices, edges) {
const adjList = new Map();
for (let i = 0; i < numVertices; i++) {
adjList.set(i, []);
}
for (const [u, v] of edges) {
adjList.get(u).push(v);
adjList.get(v).push(u); // Add reverse edge for undirected graph!
}
return adjList;
}
const graph = buildGraph(4, [[0, 1], [0, 2], [1, 3], [2, 3]]);
console.log(graph.get(0)); // Output: [1, 2]
| Feature | Adjacency List | Adjacency Matrix |
|---|---|---|
| Space Complexity | O(V + E) (Optimal for sparse graphs) | O(V^2) (Heavy memory) |
Check Edge (u, v) | O(Degree(u)) | O(1) (matrix[u][v] === 1) |
| Iterate Neighbors | O(Degree(u)) | O(V) (Scan entire row) |
V = 100,000 and E = 200,000, an adjacency matrix requires 100,000^2 = 10 billion cells (40 GB RAM), crashing instantly! Always default to Adjacency Lists.Use adjacency lists for network representations. Next, let's explore Graph Traversals: BFS & DFS!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.