Graph Representation
EasyAdjacency list or adjacency matrix
Problem
Represent a graph using an adjacency matrix or adjacency list, and know their trade-offs.
Store connections as a grid (matrix) or per-node neighbour lists.
The idea
An adjacency list stores each vertex's neighbours in O(V + E) space and iterates them directly, which is what traversals need. A matrix uses O(V²) but answers 'is there an edge between these two?' in O(1), which only pays off on dense graphs.
The trick
- List for sparse graphs and traversal; matrix for dense graphs and edge queries.
- Undirected edges must be inserted in both directions.
- Weights ride along as pairs in the list, or as values in the matrix.
Step 1 of 5. A graph is dots (nodes) joined by lines (edges). Think of people and their friendships.
1/5
Optimal
timeO(V+E)spaceO(V+E)
Neighbors per node.
1const adj = Array.from({length: V}, () => []);2for (const [u, v] of edges) {3 adj[u].push(v);4 adj[v].push(u); // omit for directed5}Input
- nodes
- 5, 5 edges
Memory
- visiting
- —
Output
- reached
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- edges [[0,1],[0,2]]
- Output:
- adjacency list 0:[1,2]
Finished the walkthrough? Add it to your streak.