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 Columbus, a library here, a community center 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, German Village, Bexley, Short North, Grandview, Hilltop and Clintonville, 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 Hilltop, for example.

A map-like drawing of seven circles: Shop, German Village, Bexley, Short North, Grandview, Hilltop and Clintonville. Lines between them are labeled with minutes: Shop to German Village 9, Shop to Bexley 11, German Village to Bexley 7, German Village to Short North 12, Shop to Short North 23, Short North to Grandview 10, Grandview to Hilltop 14, Short North to Hilltop 26, Bexley to Clintonville 18, Shop to Clintonville 31.
The Saturday pickup graph: seven places and ten roads, weighted by riding minutes

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 neighbors. 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 neighbors of this vertex: answering it means scanning every edge, O(E).

Java Example · Main.java
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", "German Village", 9), new Road("Shop", "Bexley", 11), new Road("German Village", "Bexley", 7),
                new Road("German Village", "Short North", 12), new Road("Shop", "Short North", 23), new Road("Short North", "Grandview", 10),
                new Road("Grandview", "Hilltop", 14), new Road("Short North", "Hilltop", 26), new Road("Bexley", "Clintonville", 18),
                new Road("Shop", "Clintonville", 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 = "German Village";
        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);
    }
}
Output
10 roads
riding every road once: 161 minutes
adjacent to German Village: [Shop, Bexley, Short North]

What this code does

The roads are stored as a list of records, one per edge, with both ends and the riding time. Totaling the minutes is a single pass over the list. Finding the neighbors of German Village 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 neighbors 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.

Java Example · Main.java
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", "German Village", 9), new Road("Shop", "Bexley", 11), new Road("German Village", "Bexley", 7),
                new Road("German Village", "Short North", 12), new Road("Shop", "Short North", 23), new Road("Short North", "Grandview", 10),
                new Road("Grandview", "Hilltop", 14), new Road("Short North", "Hilltop", 26), new Road("Bexley", "Clintonville", 18),
                new Road("Shop", "Clintonville", 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);
        }
    }
}
Output
Shop (degree 4): German Village=9 Bexley=11 Short North=23 Clintonville=31
German Village (degree 3): Shop=9 Bexley=7 Short North=12
Bexley (degree 3): Shop=11 German Village=7 Clintonville=18
Short North (degree 4): German Village=12 Shop=23 Grandview=10 Hilltop=26
Grandview (degree 2): Short North=10 Hilltop=14
Hilltop (degree 2): Grandview=14 Short North=26
Clintonville (degree 2): Bexley=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 Grandview, Hilltop and Clintonville 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 neighbors means reading its whole row, O(V). Matrices suit small or dense graphs; adjacency lists suit large sparse ones.

Java Example · Main.java
public class Main {
    public static void main(String[] args) {
        String[] places = {"Shop", "German Village", "Bexley", "Short North", "Grandview", "Hilltop", "Clintonville"};
        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));
    }
}
Output
   0   9  11  23   0   0  31   0 Shop
   9   0   7  12   0   0   0   1 German Village
  11   7   0   0   0   0  18   2 Bexley
  23  12   0   0  10  26   0   3 Short North
   0   0   0  10   0  14   0   4 Grandview
   0   0   0  26  14   0   0   5 Hilltop
  31   0  18   0   0   0   0   6 Clintonville
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.

The same small graph of four vertices A, B, C and D, with edges A-B 5, A-C 2, C-D 4, drawn three ways side by side. Left: an edge list of three rows. Middle: an adjacency list, with A pointing to B=5 and C=2, B to A=5, C to A=2 and D=4, D to C=4. Right: a 4 by 4 matrix with the weights in the matching cells and zeros elsewhere, symmetric about the diagonal.
One graph, three representations: edge list, adjacency list and adjacency matrix
Comparing graph representations
OperationEdge listAdjacency listAdjacency matrix
MemoryO(E)O(V + E)O(V²)
Are u and v adjacent?O(E)O(degree of u)O(1)
List the neighbors of uO(E)O(degree of u)O(V)
Add an edgeO(1)O(1)O(1)
Visit every edgeO(E)O(V + E)O(V²)
Best forReading files, sorting edges by weightMost algorithms on sparse graphsSmall 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.

Java Example · Main.java
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);
    }
}
Output
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, Short North 4 and Clintonville 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", "German Village", 9), new Road("Shop", "Bexley", 11), new Road("German Village", "Bexley", 7),
                new Road("German Village", "Short North", 12), new Road("Shop", "Short North", 23), new Road("Short North", "Grandview", 10),
                new Road("Grandview", "Hilltop", 14), new Road("Short North", "Hilltop", 26), new Road("Bexley", "Clintonville", 18),
                new Road("Shop", "Clintonville", 31));
        for (String p : List.of("Shop", "Short North", "Clintonville")) 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 neighbors 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 neighbor questions.
  • An adjacency list maps each vertex to its edges, uses O(V + E) memory and lists neighbors 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.

  1. 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.

  2. How many cells does an adjacency matrix for 1,000 vertices have?

    Show answer

    1,000,000.

  3. What is the degree of the Shop in the pickup graph?

    Show answer

    4.

  4. Which representation answers are u and v adjacent fastest?

    Show answer

    The adjacency matrix, in O(1).

  5. 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.

Take the quiz