Representing graphs

Written Explanation

The adjacency list

An adjacency list stores, for each node, the list of nodes it has an edge to. Take the graph with edges A-B, A-C, B-D, C-D, and D-E (all undirected). Its adjacency list is:

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C, E]
E: [D]

Each line answers one question: "who are my neighbors?" To visit the neighbors of D you read one short list. You never look at nodes that are not connected to D. Think of it as the printed list of connections beside each station on a metro map.

The total number of entries in an adjacency list depends on the edges. With V nodes and E edges, the list holds V entries and, for an undirected graph, 2 E neighbor slots (each edge is recorded at both ends). The memory is therefore proportional to V + E, which is small for graphs where each node has only a few neighbors.

In Java: Map of Lists

The natural Java type is a map from a node's name to the list of its neighbors:

Map<String, List<String>> g = new HashMap<>();

The key is the node, and the value is its neighbor list. Nodes here are Strings such as station names; any type with proper equals and hashCode works as a key, as the hashing module taught.

Adding the first neighbor to a node that has no entry yet is the awkward moment. g.get("A") would return null, and calling .add(...) on null throws a NullPointerException. The method computeIfAbsent solves this: if the key is absent, it creates the value with the function you give it, stores it, and returns it. The documentation describes it as computing and storing a value only when the key has no mapping.

g.computeIfAbsent("A", k -> new ArrayList<>()).add("B");

Read this as: "get the list for A, creating an empty one if there is none, then add B to it."

Undirected and directed edges in code

For an undirected edge, the relationship goes both ways, so we record it in both lists:

static void addUndirected(String a, String b) {
    g.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
    g.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
}

For a directed edge from from to to, only from gets to in its list. We also make sure to exists as a node, with an empty list if it has no outgoing edges:

static void addDirected(String from, String to) {
    g.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
    g.computeIfAbsent(to, k -> new ArrayList<>());
}

That second line matters. A node that nothing leaves, such as a library that needs nothing else, must still be a key in the map. Otherwise code that loops over g.keySet() would never see it.

Reading neighbors safely

When code asks for the neighbors of a node, two things can go wrong: the node is not in the graph, or it is there with no neighbors. Use getOrDefault so both cases give an empty list instead of null:

for (String next : g.getOrDefault(node, List.of())) { ... }

getOrDefault(key, defaultValue) returns the default when the map has no mapping for the key. List.of() is an immutable empty list: safe to loop over, but you must never try to add to it. Add to graphs only through computeIfAbsent.

The adjacency matrix

The other classic representation is the adjacency matrix: a square grid where row i, column j says whether there is an edge from node i to node j. Nodes must be numbered 0, 1, 2, and so on.

boolean[][] m = new boolean[3][3];   // nodes 0, 1, 2
m[0][1] = true;                      // edge 0 - 1
m[1][0] = true;                      // undirected: set both cells

Printing Arrays.deepToString(m) for this example gives [[false, true, false], [true, false, false], [false, false, false]].

The matrix answers "is there an edge between i and j?" in one array lookup, which is fast. But it needs V x V cells no matter how few edges exist, and listing the neighbors of one node means scanning a whole row of V cells.

Which one to choose

Reference material on graph representations makes the same point: the list's space is proportional to nodes plus edges while the matrix's is proportional to the square of the nodes, so the list wins when the graph is sparse. A metro network with 1,000 stations might have 1,100 tracks. A matrix would need a million cells, almost all false. A list holds roughly 2,200 neighbor entries. Most real graphs are sparse: people do not know most other people, and a service calls a handful of others. This course uses the adjacency list from now on.