Start here: what this lesson is for
Graphs have a reputation for being the hard chapter. They are not harder than trees - they are trees with two rules removed, and the difficulty is almost entirely about recognising a graph rather than traversing one.
Most problems labelled hard are graph problems that nobody described as graphs. A grid of cells, a list of course prerequisites, a friend network, the states of a puzzle - all graphs, none of them announced.
So this lesson spends its time on representation and recognition. Once you can look at a word problem and say what the nodes are and what the edges are, the traversal is the easy part - and the next lesson shows it is the same eight lines you already know.
- What you need first: chapters 7 and 8 - stacks, queues and tree traversal.
- What you will be able to do: model an unfamiliar problem as nodes and edges.
- How long: about 22 minutes, plus two problems at the end.
- graph
- - nodes joined by edges, with no root and cycles allowed
A tree that stopped being polite
A tree has rules: one root, one parent each, no loops. Remove those rules and you have a graph - just nodes, and connections between them. Any node may link to any other, cycles are allowed, and there need not be a top.
That sounds like a small change and it is the whole chapter. Without a root you have to choose where to start; without the no-cycles rule you must remember where you have been, or you will loop forever.
The payoff for that difficulty is reach. Roads between cities, friendships, web links, task dependencies, the moves available in a puzzle, even a grid of pixels - all graphs. When a problem feels hard and unlike anything you have seen, the useful first question is: what are the nodes, and what are the edges?
Imagine it like this: A map of cities joined by roads. No city is 'the first one', you can drive in circles, and getting somewhere means choosing a route rather than following the only one.
- node (vertex)
- - one thing in the graph - a city, a person, a state
- edge
- - a connection between two nodes
- directed
- - edges point one way, like a one-way street or a dependency
- weighted
- - edges carry a cost - distance, time, price
Two ways to store one
An adjacency matrix is a grid: m[i][j] is true when i connects to j. Checking whether two nodes are joined is instant, and that is its entire advantage. The cost is memory - n squared booleans regardless of how few edges exist - so a million-user social network would need a trillion cells to store a handful of friendships each.
An adjacency list stores, for each node, only the neighbours it actually has. Memory is proportional to the edges that exist, and walking a node's neighbours - which is what every traversal does constantly - is direct.
Real graphs are sparse: people have hundreds of friends, not millions; cities have a few roads each. So the adjacency list is the default, and the matrix earns its place only on small, dense graphs where you constantly ask 'are these two connected?'.
// adjacency list: node -> its neighbours
Map<Integer, List<Integer>> graph = new HashMap<>();
void addEdge(int a, int b) {
graph.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
graph.computeIfAbsent(b, k -> new ArrayList<>()).add(a); // undirected:
// add BOTH ways
}
addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(3, 4);1 -> [2, 3] 2 -> [1, 4] 3 -> [1, 4] 4 -> [2, 3] adjacency list 4 nodes, 4 edges -> 8 entries stored adjacency matrix 4 nodes -> 16 cells stored at 1,000,000 nodes: list ~ edges, matrix ~ 10^12 cells
- adjacency list
- - each node stores only its actual neighbours - the default
- adjacency matrix
- - an n by n grid of connections - fast lookup, heavy memory
- sparse
- - far fewer edges than the maximum possible - almost every real graph
The grid nobody calls a graph
Here is the recognition that unlocks a whole tier of problems. A grid is a graph. Each cell is a node, and its edges are the neighbouring cells you are allowed to move to - usually up, down, left and right.
You never build the adjacency list. The neighbours are computed on demand from the coordinates, which is why these problems look like nested loops rather than graph theory. 'Number of islands', 'flood fill', 'shortest path through a maze', 'rotting oranges' are all standard graph traversals wearing a grid costume.
Once you see it, the solution stops being clever and becomes mechanical: it is BFS or DFS over cells, with a rule about which neighbours are legal.
// the four moves - the "edges" of a grid node
int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
List<int[]> neighbours(char[][] grid, int r, int c) {
List<int[]> out = new ArrayList<>();
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= grid.length) continue; // off the top/bottom
if (nc < 0 || nc >= grid[0].length) continue; // off the sides
if (grid[nr][nc] == '0') continue; // water: not an edge
out.add(new int[]{nr, nc});
}
return out;
}grid neighbours(1,1)
1 1 0 (0,1) up
1 1 0 (2,1) down
0 0 1 (1,0) left
(1,2) is '0' -> not a neighbour- A graph is nodes + edges: no root, cycles allowed
- Adjacency list by default; matrix only for small dense graphs
- Undirected edges must be added in both directions
- Grids, dependencies and state machines are all graphs
Directed, undirected, weighted: the three questions to ask
Before writing any graph code, answer three questions about the problem. Getting one wrong produces code that runs happily and returns the wrong answer, which is worse than a crash.
Is it directed? Roads can be one-way; friendships usually go both ways; 'A must happen before B' is emphatically one-way. An undirected edge must be added in both directions, and forgetting the second line is the single most common graph bug.
Is it weighted? If every edge costs the same, BFS finds shortest paths for free. If edges carry different costs, BFS is simply wrong and you need Dijkstra - which is the lesson after next.
Can it have cycles? Almost always yes, and that is why every traversal needs a visited set. A tree traversal can skip it; a graph traversal that skips it loops forever - a hang, not a crash, which is harder to diagnose.
// UNDIRECTED - both directions, always
void addUndirected(Map<Integer,List<Integer>> g, int a, int b) {
g.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
g.computeIfAbsent(b, k -> new ArrayList<>()).add(a); // <- forgetting this
} // is the classic bug
// DIRECTED - one direction only
void addDirected(Map<Integer,List<Integer>> g, int from, int to) {
g.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
}
// WEIGHTED - the edge carries a cost
void addWeighted(Map<Integer,List<int[]>> g, int a, int b, int cost) {
g.computeIfAbsent(a, k -> new ArrayList<>()).add(new int[]{b, cost});
}friendship undirected, unweighted -> BFS for degrees of separation prerequisites directed, unweighted -> topological sort road network undirected, weighted -> Dijkstra web links directed, unweighted -> BFS or DFS get "undirected" wrong -> half your graph is invisible get "weighted" wrong -> BFS confidently returns a WRONG shortest path
- degree
- - how many edges a node has - in-degree and out-degree when directed
Recap: modelling is the hard part
The traversal code in the next lesson is eight lines and you will reuse it unchanged for years. The skill this lesson is building is the one that comes before it.
Store graphs as adjacency lists by default - memory proportional to the edges that actually exist. A matrix only earns its place on small dense graphs where you constantly ask 'are these two connected?'.
Remember that grids are graphs with the adjacency computed rather than stored, which is why island and maze problems look like nested loops and are really traversals.
And answer the three questions before writing anything, because the wrong answer there produces confidently wrong output rather than an error.
- Nodes + edges, no root, cycles allowed
- Adjacency list by default; matrix for small dense graphs
- Undirected edges must be added BOTH ways
- Grids, dependencies and state machines are all graphs
- Ask directed / weighted / cyclic before choosing an algorithm
Your turn
Reading is not learning. Open each one in NeonFlow and watch your own code run, step by step.
Build the adjacency list
Turn a list of edges into an adjacency list for an undirected graph, then print each node's neighbours. Deliberately comment out the second add() line and run it - watch half the graph disappear.
import java.util.*;
public class BuildGraph {
static Map<Integer, List<Integer>> build(int[][] edges) {
Map<Integer, List<Integer>> g = new HashMap<>();
for (int[] e : edges) {
// TODO: add e[1] as a neighbour of e[0]
// TODO: and e[0] as a neighbour of e[1] <- undirected!
}
return g;
}
public static void main(String[] args) {
Map<Integer, List<Integer>> g =
build(new int[][]{{1,2},{1,3},{2,4},{3,4}});
for (int node : new TreeSet<>(g.keySet())) {
System.out.println(node + " -> " + g.get(node));
}
// expect 1 -> [2, 3] 2 -> [1, 4] 3 -> [1, 4] 4 -> [2, 3]
}
}Treat a grid as a graph
Write neighbours(row, col) for a grid: the up/down/left/right cells that are on the board and are land. There is no adjacency list anywhere - the edges are computed from the coordinates, which is the recognition this whole lesson is about.
import java.util.*;
public class GridGraph {
static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
static List<int[]> neighbours(char[][] grid, int r, int c) {
List<int[]> out = new ArrayList<>();
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
// TODO: skip if off the top or bottom
// TODO: skip if off the left or right
// TODO: skip if the cell is water ('0')
out.add(new int[]{nr, nc});
}
return out;
}
public static void main(String[] args) {
char[][] grid = {
{'1','1','0'},
{'1','1','0'},
{'0','0','1'},
};
for (int[] n : neighbours(grid, 1, 1)) {
System.out.println("(" + n[0] + "," + n[1] + ")");
}
// expect (0,1) (2,1)? no - (2,1) is water. expect (0,1) and (1,0)
}
}