Algorithms from zero
Graph representations
You know trees: a root at the top, children below, edges pointing downward. A tree is a special graph—one where there is exactly one path between any two nodes and no cycles. Now relax that rule. A graph is any collection of vertices (nodes) connected by edges—with no restriction. You can have cycles (A → B → A), multiple paths between nodes, edges pointing both ways (or one way), and weights on edges. Graphs are everywhere: road networks (cities are vertices, roads are edges), social networks (people are vertices, friendships are edges), the web (pages are vertices, links are edges). Before you can search a graph, find a path, or compute anything, you must choose how to represent it in memory. This lesson covers the two main representations: adjacency list and adjacency matrix. Each trades space for time in a different way.
After this lesson you can define a graph and its vocabulary (vertex, edge, neighbor, degree, path, cycle, connected). You can distinguish directed from undirected, weighted from unweighted. You can build an adjacency list in code (array/map from vertex to list of neighbors) and read the result—knowing it uses O(V + E) space and allows you to iterate a vertex’s neighbors in O(degree) time. You can build an adjacency matrix (V×V grid where cell [u][v] marks an edge) and understand it uses O(V²) space but answers “is there an edge u-v?” in O(1) time. You can compare the tradeoffs: list wins for sparse graphs (few edges), matrix wins for dense graphs (many edges) and for fast edge lookup. You trace both representations on a concrete graph, and you can code both. You recognize that trees are graphs with no cycles. Next lesson is depth-first search (DFS), where you explore a graph edge by edge.
What is a graph?
A graph is a pair (V, E):
- V: a set of vertices (or nodes). Example:
{A, B, C, D}. - E: a set of edges connecting pairs of vertices. Example:
{(A, B), (B, C), (C, D), (D, A)}.
Visual:
A --- B
| |
D --- CHere, V = {A, B, C, D} and E = {(A, B), (B, C), (C, D), (D, A)}.
Key terminology
- Edge: A connection between two vertices.
- Vertex (or node): A point in the graph.
- Neighbor (or adjacent): If there is an edge (u, v), then u and v are neighbors; v is adjacent to u.
- Degree of a vertex: The number of edges connected to it. In the square above, each vertex has degree 2.
- Path: A sequence of vertices where consecutive vertices are neighbors. Example: A → B → C is a path.
- Cycle: A path that starts and ends at the same vertex, with at least one edge. Example: A → B → C → D → A is a cycle.
- Connected (undirected): A graph where there is a path between every pair of vertices.
Directed vs. undirected
- Undirected: An edge (A, B) means you can go from A to B and from B to A. It is symmetric.
- Directed: An edge A → B means you can go from A to B only. It is one-way. Often called a digraph.
Example:
Undirected: A --- B Directed: A --> B
^ |
+---- CIn the undirected graph, you can traverse A ↔ B. In the directed graph, you can go A → B → C, but not back from C to A (no edge C → A).
Weighted vs. unweighted
- Unweighted: Each edge has no value; either it exists or it does not.
- Weighted: Each edge has a numeric weight (cost, distance, capacity). Example: a road network where the weight is the distance in km.
Example:
Unweighted: A --- B Weighted: A --5-- B
| /
3 2
| /
C----Trees are graphs
A tree is a graph with no cycles. More precisely: a tree is a connected graph with V vertices and exactly V-1 edges. A tree has no cycles, and there is exactly one path between any two vertices.
Two representations: adjacency list and adjacency matrix
Graphs are abstract. To work with them in code, you must choose a concrete representation. Two main choices:
- Adjacency list: For each vertex, store the list of its neighbors (or outgoing edges).
- Adjacency matrix: A V×V grid where cell [u][v] indicates whether there is an edge from u to v.
We will detail both.
Example graph for both representations
Let’s use a simple directed graph with 4 vertices (0, 1, 2, 3) and 5 edges:
0 → 1
0 → 2
1 → 3
2 → 3
3 → 2Visual:
0 → 1
↓ ↓
2 → 3
↑ ↓
+---+Representation 1: Adjacency List
For each vertex, list its neighbors (outgoing edges).
0: [1, 2]
1: [3]
2: [3]
3: [2]In code, use an array of arrays, an array of maps, or a map of lists (depending on your language and whether vertices are 0-indexed integers or labels like “A”, “B”, “C”).
Representation 2: Adjacency Matrix
A 4×4 matrix. Cell [u][v] = 1 if there is an edge u → v, else 0.
0 1 2 3
0 0 1 1 0
1 0 0 0 1
2 0 0 0 1
3 0 0 1 0Row 0 is [0, 1, 1, 0]: vertex 0 points to 1 and 2. Row 1 is [0, 0, 0, 1]: vertex 1 points to 3. Row 3 is [0, 0, 1, 0]: vertex 3 points to 2.
The edge list (brief mention)
A third representation: a list of edges. Example: [(0, 1), (0, 2), (1, 3), (2, 3), (3, 2)]. This is rarely the primary representation for general graph work, but it is used in some specialized algorithms (like Kruskal’s for minimum spanning trees).
Building an adjacency list
1
// For a directed graph with V vertices (0 to V-1)
2
function buildAdjacencyList(V, edges) {
3
// Create array of lists (one per vertex)
4
const adj = Array.from({ length: V }, () => []);
5
6
// For each edge [u, v], add v to the neighbor list of u
7
for (const [u, v] of edges) {
8
adj[u].push(v);
9
}
10
11
return adj;
12
}
13
14
// Example: graph with 4 vertices, 5 edges
15
const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 2]];
16
const adj = buildAdjacencyList(4, edges);
17
console.log(adj);
18
// Output:
19
// [ [1, 2], [3], [3], [2] ]
- L3 Create an array of V empty lists, one per vertex.
- L6 For each edge (u, v), append v to the list of u.
- L11 This graph has edges 0→1, 0→2, 1→3, 2→3, 3→2.
- L12 adj[0] = [1, 2]: vertex 0 has neighbors 1 and 2.
Building an adjacency matrix
1
// For a directed graph with V vertices (0 to V-1)
2
function buildAdjacencyMatrix(V, edges) {
3
// Create V×V matrix, initialized to 0
4
const adj = Array.from({ length: V }, () => Array(V).fill(0));
5
6
// For each edge [u, v], set adj[u][v] = 1
7
for (const [u, v] of edges) {
8
adj[u][v] = 1;
9
}
10
11
return adj;
12
}
13
14
// Example: same graph
15
const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 2]];
16
const adj = buildAdjacencyMatrix(4, edges);
17
console.log(adj);
18
// Output:
19
// [ [ 0, 1, 1, 0 ],
20
// [ 0, 0, 0, 1 ],
21
// [ 0, 0, 0, 1 ],
22
// [ 0, 0, 1, 0 ] ]
- L3 Create a V×V matrix, all cells initially 0.
- L6 For each edge (u, v), set cell [u][v] = 1.
- L14 adj[0][1] = 1: there is an edge from 0 to 1.
1
edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 2]];
2
adj_list = buildAdjacencyList(4, edges);
3
adj_matrix = buildAdjacencyMatrix(4, edges);
Adjacency list: O(V + E) space, fast neighbor iteration
You store one entry per vertex, plus one entry per edge. Total: V + E entries.
- Space: O(V + E). For sparse graphs (E ≪ V²), this is much smaller than O(V²).
- Iterate neighbors of u: O(degree(u)). You just read the list of u.
- Check if edge (u, v) exists?: O(degree(u)). You must scan u’s neighbor list.
- Insert/delete edge: O(degree(u)) to find and remove. For some variants, O(1) if you use a set instead of a list.
Example: a tree with 1,000 vertices has exactly 999 edges. Adjacency list uses O(1000 + 999) ≈ 2000 space. Adjacency matrix would use 1000² = 1,000,000 cells.
Adjacency matrix: O(V²) space, O(1) edge lookup
You store a V×V grid.
- Space: O(V²). Always, regardless of the number of edges.
- Check if edge (u, v) exists?: O(1). Just look at cell [u][v].
- Iterate neighbors of u: O(V). You must scan row u.
- Insert/delete edge: O(1). Just set or clear cell [u][v].
Example: the same 1,000-vertex tree wastes 1,000,000 cells even though only 999 are used.
When to use each
| Operation | Adjacency List | Adjacency Matrix |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Iterate neighbors of u | O(degree(u)) | O(V) |
| Check “edge (u, v)?” | O(degree(u)) | O(1) |
| Insert/delete edge | O(degree(u)) or O(1) | O(1) |
| Best for | Sparse graphs | Dense graphs |
Sparse vs. dense
- Sparse: Few edges, E ≈ O(V). Use adjacency list. Space O(V), time to check edge O(V) (small lists).
- Dense: Many edges, E ≈ O(V²). Use adjacency matrix. Space is already V², and fast edge lookup is worth it.
- General rule: If E ≈ V or E < V log V, prefer adjacency list. If E > V² / 4, prefer adjacency matrix.
What is the space complexity of an adjacency list for a directed graph with V vertices and E edges?
In an adjacency matrix, how much time does it take to check whether there is an edge from vertex u to vertex v?
To iterate all neighbors of a vertex u, which representation is typically faster: adjacency list or adjacency matrix?
A graph has 5 vertices and 6 edges. How much space does an adjacency list use versus an adjacency matrix?
In a directed graph, the in-degree of a vertex is the number of incoming edges. With an adjacency list, how would you find the in-degree of a vertex u?
A graph has V = 100 vertices. For what number of edges E does an adjacency list use the same space as an adjacency matrix?
lesson.inset.undefined
Why representations matter. The same graph can be implemented two ways, with vastly different performance. If your algorithm checks “does edge (u, v) exist?” millions of times, an adjacency matrix is a game-changer. If you frequently iterate all neighbors, an adjacency list wins. Most real-world networks (social graphs, road networks, the web) are sparse—billions of nodes, but not all pairs connected—so adjacency lists dominate. But if you are working with a small, dense graph (like a complete graph), the matrix is simpler and faster.
lesson.inset.undefined
Confusing “visiting an edge” with “visiting neighbors.” When you build an adjacency list from a list of edges, you iterate edges (not vertices). If you see E edges, you iterate E times. But when you use the list to iterate neighbors of a vertex u, the time depends on the degree of u, not on E. A vertex with degree 2 has 2 neighbors, even if the graph has 1000 edges.
lesson.inset.undefined
Disconnected graphs. A graph is disconnected if some vertices have no path to others. Both representations handle this fine: a vertex might have no neighbors (empty list, or a row of zeros in the matrix). The graph is simply not fully connected. You can still ask “is there an edge (u, v)?” and get “no.”
lesson.inset.undefined
Undirected graphs. If the graph is undirected, an edge (u, v) means you can go both ways: u → v and v → u. In an adjacency list, you must add both (u to v’s list and v to u’s list). In a matrix, set both [u][v] and [v][u] to 1. This doubles the space (or memory) relative to a directed graph with the same edges, but the representations stay the same—just symmetrical.
Explain what an adjacency list and an adjacency matrix are, and describe the key tradeoff between them.
A graph is vertices + edges. Distinguish directed (one-way) from undirected (symmetric), and weighted (edges have costs) from unweighted. Use vocabulary: vertex, neighbor, degree, path, cycle.
Two main representations:
- Adjacency list: For each vertex, list its neighbors. O(V + E) space. Fast neighbor iteration O(degree(u)), slow edge lookup O(degree(u)).
- Adjacency matrix: V×V grid, cell [u][v] = 1 if edge exists. O(V²) space. Instant edge lookup O(1), slow neighbor iteration O(V).
Choose list for sparse graphs (few edges), matrix for dense graphs or if edge-lookup speed is critical. A tree is a graph with no cycles—it is sparse (E = V - 1).
Next: depth-first search (DFS)—how to explore a graph by following edges and visiting every reachable vertex.