JAVA-205 · Lesson 7 of 12 · 21 min
Graphs and their representations
▶ Video coming soon A video version of this lesson is on the way.
Every Saturday morning, two volunteers ride Second Gear's cargo bike and trailer to partner drop-off sites around Hamilton, a library here, a community centre there, to collect donated bikes and parts. Kofi plans the route on a paper map and a lot of guessing. Starting on Tuesday, November 2, 2027, after reading week, Ingrid spends three sessions on the data structure behind every map, network and route planner: the graph. Tonight is about representing one; the next two lessons search it.
Vertices and edges
A graph is a set of vertices (also called nodes) and a set of edges that connect pairs of vertices. In the pickup map, the vertices are the shop and the six partner sites, and an edge joins two places when there is a reasonable cargo-bike route between them. Each edge carries a weight: the riding time in minutes. The same structure describes very different things: computers and network links, people and friendships, parts and the assemblies they belong to, tasks and the tasks they must wait for.
Kofi's map has seven vertices: the Shop, Corktown, Crown Point, Kirkendall, Westdale, Dundas and Stoney Creek, and ten roads between them. Some places are directly connected and others are reached through a third site; there is no direct road from the Shop to Dundas, for example.
The vocabulary of graphs
A few terms come up constantly. In an undirected graph an edge goes both ways, like a road you can ride in either direction. In a directed graph each edge has a direction, like a one-way street or a task that must come before another; directed edges are often called arcs. Two vertices joined by an edge are adjacent, or neighbours. The degree of a vertex is the number of edges touching it. A path is a sequence of vertices in which each consecutive pair is joined by an edge, and a cycle is a path that returns to its start. A graph is connected if there is a path between every pair of vertices. A connected graph with no cycles is a tree, the shape Tamsin's assemblies had in lesson 5.
Two numbers describe a graph's size: V, the number of vertices, and E, the number of edges. Graph algorithms are measured in terms of both. A graph with E close to the largest possible, V(V − 1)/2 for an undirected graph, is dense; one with E closer to V is sparse. Road maps and most real networks are sparse: each place connects to only a handful of others, however large the map.
An edge list
The simplest way to store a graph is an edge list: a list of records, each holding the two ends and the weight. It is easy to build from a file and easy to sort, for example by weight. But it is slow for the most common question a graph algorithm asks, which is what are the neighbours of this vertex: answering it means scanning every edge, O(E).
import java.util.*;
public class Main {
record Road(String from, String to, int minutes) {}
public static void main(String[] args) {
List<Road> roads = List.of(
new Road("Shop", "Corktown", 9), new Road("Shop", "Crown Point", 11), new Road("Corktown", "Crown Point", 7),
new Road("Corktown", "Kirkendall", 12), new Road("Shop", "Kirkendall", 23), new Road("Kirkendall", "Westdale", 10),
new Road("Westdale", "Dundas", 14), new Road("Kirkendall", "Dundas", 26), new Road("Crown Point", "Stoney Creek", 18),
new Road("Shop", "Stoney Creek", 31));
System.out.println(roads.size() + " roads");
int total = 0;
for (Road r : roads) total += r.minutes();
System.out.println("riding every road once: " + total + " minutes");
String place = "Corktown";
List<String> adjacent = new ArrayList<>();
for (Road r : roads) {
if (r.from().equals(place)) adjacent.add(r.to());
else if (r.to().equals(place)) adjacent.add(r.from());
}
System.out.println("adjacent to " + place + ": " + adjacent);
}
}10 roads riding every road once: 161 minutes adjacent to Corktown: [Shop, Crown Point, Kirkendall]
What this code does
The roads are stored as a list of records, one per edge, with both ends and the riding time. Totalling the minutes is a single pass over the list. Finding the neighbours of Corktown also needs a pass over every road, because the edge list has no way to jump to one place's edges.
An adjacency list
The standard representation for sparse graphs is the adjacency list: for each vertex, a list of its edges. In Java this is naturally a Map from a vertex to a List of edges. Finding a vertex's neighbours is then a map lookup followed by a walk over just its own edges, O(degree). The whole structure uses O(V + E) memory. For an undirected graph, each road is stored twice, once in the list of each end.
import java.util.*;
public class Main {
record Road(String from, String to, int minutes) {}
record Edge(String to, int minutes) {}
public static void main(String[] args) {
List<Road> roads = List.of(
new Road("Shop", "Corktown", 9), new Road("Shop", "Crown Point", 11), new Road("Corktown", "Crown Point", 7),
new Road("Corktown", "Kirkendall", 12), new Road("Shop", "Kirkendall", 23), new Road("Kirkendall", "Westdale", 10),
new Road("Westdale", "Dundas", 14), new Road("Kirkendall", "Dundas", 26), new Road("Crown Point", "Stoney Creek", 18),
new Road("Shop", "Stoney Creek", 31));
Map<String, List<Edge>> graph = new LinkedHashMap<>();
for (Road r : roads) {
graph.computeIfAbsent(r.from(), k -> new ArrayList<>()).add(new Edge(r.to(), r.minutes()));
graph.computeIfAbsent(r.to(), k -> new ArrayList<>()).add(new Edge(r.from(), r.minutes()));
}
for (var entry : graph.entrySet()) {
StringBuilder line = new StringBuilder(entry.getKey() + " (degree " + entry.getValue().size() + "):");
for (Edge e : entry.getValue()) line.append(" ").append(e.to()).append("=").append(e.minutes());
System.out.println(line);
}
}
}Shop (degree 4): Corktown=9 Crown Point=11 Kirkendall=23 Stoney Creek=31 Corktown (degree 3): Shop=9 Crown Point=7 Kirkendall=12 Crown Point (degree 3): Shop=11 Corktown=7 Stoney Creek=18 Kirkendall (degree 4): Corktown=12 Shop=23 Westdale=10 Dundas=26 Westdale (degree 2): Kirkendall=10 Dundas=14 Dundas (degree 2): Westdale=14 Kirkendall=26 Stoney Creek (degree 2): Crown Point=18 Shop=31
What this code does
Each road is added to the list of both of its ends, so the graph can be followed in either direction. A LinkedHashMap keeps the places in the order they were first seen, which makes the printout repeatable. The Shop has the highest degree, 4, and Westdale, Dundas and Stoney Creek have the lowest, 2.
computeIfAbsent creates the empty list the first time a place is seen, which saves a separate check. The choice of LinkedHashMap rather than HashMap is deliberate: as JAVA-201 stressed, a HashMap's iteration order is unspecified, and a program whose output changes order between JDK versions is hard to test. When the vertices are numbered 0 to V − 1 instead of named, the adjacency list is often an array or List of lists, which is a little faster.
An adjacency matrix
The other classic representation is the adjacency matrix: a V × V table where the cell in row i, column j holds the weight of the edge from vertex i to vertex j, or a marker such as 0 when there is none. Checking whether two particular vertices are adjacent is O(1), a single array read. But the matrix always uses V² cells, even when most are empty, and listing one vertex's neighbours means reading its whole row, O(V). Matrices suit small or dense graphs; adjacency lists suit large sparse ones.
public class Main {
public static void main(String[] args) {
String[] places = {"Shop", "Corktown", "Crown Point", "Kirkendall", "Westdale", "Dundas", "Stoney Creek"};
int[][] roads = {{0, 1, 9}, {0, 2, 11}, {1, 2, 7}, {1, 3, 12}, {0, 3, 23},
{3, 4, 10}, {4, 5, 14}, {3, 5, 26}, {2, 6, 18}, {0, 6, 31}};
int v = places.length;
int[][] m = new int[v][v];
for (int[] r : roads) {
m[r[0]][r[1]] = r[2];
m[r[1]][r[0]] = r[2];
}
for (int i = 0; i < v; i++) {
StringBuilder row = new StringBuilder();
for (int j = 0; j < v; j++) row.append(String.format("%4d", m[i][j]));
System.out.println(row + " " + i + " " + places[i]);
}
System.out.println("road from 3 to 4? " + (m[3][4] > 0) + ", from 1 to 5? " + (m[1][5] > 0));
}
}0 9 11 23 0 0 31 0 Shop 9 0 7 12 0 0 0 1 Corktown 11 7 0 0 0 0 18 2 Crown Point 23 12 0 0 10 26 0 3 Kirkendall 0 0 0 10 0 14 0 4 Westdale 0 0 0 26 14 0 0 5 Dundas 31 0 18 0 0 0 0 6 Stoney Creek road from 3 to 4? true, from 1 to 5? false
What this code does
The places are numbered 0 to 6 and each road sets two cells of a 7 by 7 int array, because the graph is undirected and the matrix is symmetric. A zero means there is no direct road. Asking whether two places are adjacent is a single array read, but 49 cells are used to store 10 roads.
| Operation | Edge list | Adjacency list | Adjacency matrix |
|---|---|---|---|
| Memory | O(E) | O(V + E) | O(V²) |
| Are u and v adjacent? | O(E) | O(degree of u) | O(1) |
| List the neighbours of u | O(E) | O(degree of u) | O(V) |
| Add an edge | O(1) | O(1) | O(1) |
| Visit every edge | O(E) | O(V + E) | O(V²) |
| Best for | Reading files, sorting edges by weight | Most algorithms on sparse graphs | Small or dense graphs |
Directed graphs
Not every relationship goes both ways. Tamsin's repair jobs have an order: a wheel must be trued before the brakes are adjusted, and the bike must be cleaned before the chain is fitted. Jobs and their must-come-before relations form a directed graph. In an adjacency list for a directed graph, each arc is stored once, in the list of the vertex it starts from. A directed graph with no cycles, a DAG, can always be put into an order in which every arc points forward, a topological order, which is how build tools such as Gradle order tasks.
import java.util.*;
public class Main {
public static void main(String[] args) {
Map<String, List<String>> before = new LinkedHashMap<>();
before.put("clean", List.of("fit chain", "adjust brakes"));
before.put("true wheel", List.of("adjust brakes"));
before.put("fit chain", List.of("adjust gears"));
before.put("adjust brakes", List.of("test ride"));
before.put("adjust gears", List.of("test ride"));
before.put("test ride", List.of());
Map<String, Integer> waitingFor = new LinkedHashMap<>();
for (String job : before.keySet()) waitingFor.putIfAbsent(job, 0);
for (List<String> next : before.values())
for (String job : next) waitingFor.merge(job, 1, Integer::sum);
System.out.println("jobs each job waits for: " + waitingFor);
Deque<String> ready = new ArrayDeque<>();
waitingFor.forEach((job, n) -> { if (n == 0) ready.add(job); });
List<String> order = new ArrayList<>();
while (!ready.isEmpty()) {
String job = ready.poll();
order.add(job);
for (String next : before.get(job))
if (waitingFor.merge(next, -1, Integer::sum) == 0) ready.add(next);
}
System.out.println("an order that works: " + order);
}
}jobs each job waits for: {clean=0, true wheel=0, fit chain=1, adjust brakes=2, adjust gears=1, test ride=2}
an order that works: [clean, true wheel, fit chain, adjust brakes, adjust gears, test ride]What this code does
Each job lists the jobs that must come after it, and the program first counts how many jobs each one is waiting for. Jobs waiting for nothing go into a queue; taking one out lowers the count of the jobs after it, and any that reach zero join the queue. The result is a topological order, which always puts the test ride last.
This method is called Kahn's algorithm, and it runs in O(V + E). If the queue empties before every job has been placed, the remaining jobs wait for each other in a cycle, and no valid order exists, which is exactly the error a build tool reports for a circular dependency.
Try it yourself
The degree of a site
Complete degree(List<Road> roads, String place) so it returns how many roads touch the given place.
The program should print Shop 4, Kirkendall 4 and Stoney Creek 2, one per line.
import java.util.*;
public class Main {
record Road(String from, String to, int minutes) {}
static int degree(List<Road> roads, String place) {
return 0;
}
public static void main(String[] args) {
List<Road> roads = List.of(
new Road("Shop", "Corktown", 9), new Road("Shop", "Crown Point", 11), new Road("Corktown", "Crown Point", 7),
new Road("Corktown", "Kirkendall", 12), new Road("Shop", "Kirkendall", 23), new Road("Kirkendall", "Westdale", 10),
new Road("Westdale", "Dundas", 14), new Road("Kirkendall", "Dundas", 26), new Road("Crown Point", "Stoney Creek", 18),
new Road("Shop", "Stoney Creek", 31));
for (String p : List.of("Shop", "Kirkendall", "Stoney Creek")) System.out.println(p + " " + degree(roads, p));
}
}Try it yourself
A row of the matrix
Build the adjacency matrix from the roads (both directions) and print, for vertex 3, the numbers of its adjacent vertices in increasing order and the total minutes of its roads.
The program should print adjacent to 3: [0, 1, 4, 5] and minutes: 71.
import java.util.*;
public class Main {
public static void main(String[] args) {
int[][] roads = {{0, 1, 9}, {0, 2, 11}, {1, 2, 7}, {1, 3, 12}, {0, 3, 23},
{3, 4, 10}, {4, 5, 14}, {3, 5, 26}, {2, 6, 18}, {0, 6, 31}};
int[][] m = new int[7][7];
List<Integer> adjacent = new ArrayList<>();
int minutes = 0;
System.out.println("adjacent to 3: " + adjacent);
System.out.println("minutes: " + minutes);
}
}Common mistakes
MistakeStoring an undirected road only in the list of one end.
InsteadAdd it to the lists of both ends, or the graph can only be followed one way.
MistakeUsing an adjacency matrix for a large sparse graph.
InsteadUse an adjacency list, which needs O(V + E) memory instead of O(V²).
MistakeIterating over a HashMap of vertices and expecting a fixed order.
InsteadUse LinkedHashMap or TreeMap when the output order matters.
MistakeAnswering what are u's neighbours by scanning the whole edge list.
InsteadBuild an adjacency list once, then look up u directly.
MistakeAssuming a directed graph can always be ordered.
InsteadOnly a DAG has a topological order; a cycle means no valid order exists.
Summary and key terms
- A graph is a set of vertices joined by edges, which can carry weights such as riding minutes.
- Graphs are undirected or directed, and their vocabulary includes adjacent vertices, degree, paths, cycles, connected graphs and trees.
- Size is measured by V vertices and E edges, and real networks are usually sparse.
- An edge list stores each edge as a record and is good for files and sorting but slow for neighbour questions.
- An adjacency list maps each vertex to its edges, uses O(V + E) memory and lists neighbours in O(degree), so it is the default for sparse graphs.
- An adjacency matrix uses a V × V table, answers adjacency in O(1) but needs O(V²) memory.
- Directed acyclic graphs model tasks that must come in order, and Kahn's algorithm finds a topological order in O(V + E) or reveals a cycle.
- Graph
- A set of vertices and a set of edges connecting pairs of them.
- Vertex
- One of the points of a graph, also called a node.
- Edge
- A connection between two vertices, possibly with a weight.
- Weight
- A number attached to an edge, such as a distance or time.
- Directed graph
- A graph whose edges have a direction.
- Degree
- The number of edges touching a vertex.
- Path
- A sequence of vertices in which each consecutive pair is joined by an edge.
- Cycle
- A path that returns to its starting vertex.
- Sparse graph
- A graph with far fewer edges than the maximum possible.
- Adjacency list
- A representation that stores, for each vertex, the list of its edges.
- Adjacency matrix
- A V × V table recording the edge, if any, between each pair of vertices.
- Topological order
- An order of the vertices of a directed acyclic graph in which every edge points forward.
Practice problems
Work each problem on paper first, then reveal the answer to check.
How many entries does an adjacency list for an undirected graph with 10 edges hold in total?
Show answer
20, because each edge appears in the lists of both its ends.
How many cells does an adjacency matrix for 1,000 vertices have?
Show answer
1,000,000.
What is the degree of the Shop in the pickup graph?
Show answer
4.
Which representation answers are u and v adjacent fastest?
Show answer
The adjacency matrix, in O(1).
What does it mean if Kahn's algorithm cannot place every job?
Show answer
The jobs that are left form a cycle, so no valid order exists.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.