☕ DSA Java Articles

Topics › Graphs › Learning

Graph Representation | Java

Easy TUF ID 2871 A2Z

Java source ↗ Edit this article ↗

What this covers

The previous lecture introduced the two classic structures, the adjacency matrix and the adjacency list. In C++ an adjacency list is one line, vector<int> adj[n]. In Java there are several reasonable ways to write it, each with its own syntax quirks, and a couple of traps that only exist in Java: generic arrays that refuse to compile, remove calls that delete the wrong element, and lists that are accidentally shared between vertices.

This article builds the same graph six ways, all with vertices 0..n-1 (LeetCode style; for 1-based input allocate n + 1 slots), each taking a directed flag. The test harness converts every one of them back to a canonical “sorted neighbours per vertex” form and checks that all six agree, on undirected, directed, empty and single-vertex graphs. The running example is the undirected graph 0-1, 0-2, 1-3, 2-3, 3-4:

0 ----- 1
|       |
|       |
2 ----- 3 ----- 4

ArrayList of ArrayLists

This is the form most Java solutions use, including GeeksforGeeks function signatures, which hand you an ArrayList<ArrayList<Integer>> adj.

static ArrayList<ArrayList<Integer>> listOfLists(int n, int[][] edges, boolean directed) {
    ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());   // every inner list must exist before use
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        if (!directed) adj.get(e[1]).add(e[0]);
    }
    return adj;
}

Two details matter. First, the outer list starts empty, so the loop that adds one inner list per vertex is mandatory; calling adj.get(3) before it runs throws IndexOutOfBoundsException. Second, the if (!directed) line is the only difference between a directed and an undirected graph: an undirected edge is two arrows.

The inner lists hold Integer objects, not ints. Java autoboxes on add and unboxes in for (int v : adj.get(u)), which is convenient but costs memory: each entry is a reference to a small object, several times the size of a raw int. For graphs up to a few hundred thousand edges this never matters. Neighbour order is insertion order, so adj.get(3) for the example is [1, 2, 4]. Traversal outputs depend on that order, which is why problems that expect a specific BFS or DFS sequence say how the lists are ordered.

In your own code, prefer declaring the type as List<List<Integer>>. The concrete type ArrayList<ArrayList<Integer>> is not a subtype of List<List<Integer>> (generics are invariant), which is why helper methods that should accept either are written with a wildcard, List<? extends List<Integer>>.

Array of lists, and why new ArrayList<Integer>[n] fails

The literal translation of vector<int> adj[n] is an array of lists, and it is slightly faster to index than a list of lists. But Java does not allow creating an array of a parameterised type: new ArrayList<Integer>[n] is a compile error (“generic array creation”). The reason is that arrays check their element type at run time while generics are erased at compile time, so the runtime could not enforce the <Integer> part. The standard workaround is to create a raw array and assign it, accepting an unchecked warning:

@SuppressWarnings("unchecked")
static List<Integer>[] arrayOfLists(int n, int[][] edges, boolean directed) {
    List<Integer>[] adj = new List[n];
    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    for (int[] e : edges) {
        adj[e[0]].add(e[1]);
        if (!directed) adj[e[1]].add(e[0]);
    }
    return adj;
}

new List[n] creates an array of nulls, so the loop filling each slot with a fresh ArrayList is again required. After that, adj[u].add(v) reads exactly like the C++ version.

A compact int[][]

When the graph is built once and only read afterwards, which is true for almost every traversal problem, you can avoid Integer boxing entirely. Count each vertex’s degree first, allocate rows of exactly that length, then fill them using a per-row cursor:

static int[][] compact(int n, int[][] edges, boolean directed) {
    int[] deg = new int[n];
    for (int[] e : edges) {
        deg[e[0]]++;
        if (!directed) deg[e[1]]++;
    }
    int[][] adj = new int[n][];
    for (int i = 0; i < n; i++) adj[i] = new int[deg[i]];
    int[] fill = new int[n];                                  // next free slot in each row
    for (int[] e : edges) {
        adj[e[0]][fill[e[0]]++] = e[1];
        if (!directed) adj[e[1]][fill[e[1]]++] = e[0];
    }
    return adj;
}

Each row is a plain int[], so iteration is fast and memory is 4 bytes per entry. Rows keep the input order, just like the list version. The cost is that you cannot add an edge later without rebuilding. Two passes over the edges are needed, which is still O(V + E).

HashMap of lists for arbitrary labels

Sometimes vertices are not 0..n-1: they might be large ids like 1000000, strings like airport codes, or nodes discovered on the fly. A Map from label to neighbour list handles that without allocating space for unused labels:

static Map<Integer, List<Integer>> mapOfLists(int[][] edges, boolean directed) {
    Map<Integer, List<Integer>> adj = new HashMap<>();
    for (int[] e : edges) {
        adj.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
        List<Integer> back = adj.computeIfAbsent(e[1], k -> new ArrayList<>());   // keeps sinks as keys too
        if (!directed) back.add(e[0]);
    }
    return adj;
}

computeIfAbsent returns the existing list or creates, stores and returns a new one, so each line both ensures the key exists and gets the list. The second call runs even for directed graphs so that a vertex with only incoming edges (a sink) still appears as a key with an empty list; otherwise iterating over adj.keySet() would silently miss it. Vertices with no edges at all never appear, so if the problem lists isolated vertices separately, add them yourself. Hash lookups are slower than array indexing, so use this form only when labels force you to.

Adjacency matrix

For dense graphs, or when the main question is “is u adjacent to v?”, a boolean[][] gives O(1) lookups at the price of O(n^2) memory:

static boolean[][] matrix(int n, int[][] edges, boolean directed) {
    boolean[][] mat = new boolean[n][n];
    for (int[] e : edges) {
        mat[e[0]][e[1]] = true;
        if (!directed) mat[e[1]][e[0]] = true;
    }
    return mat;
}

Scanning row u lists the neighbours in increasing order, not insertion order. For the star 0-3, 0-1, 0-2, the list forms give [3, 1, 2] for vertex 0, while the matrix gives [1, 2, 3]. If a problem’s expected output depends on neighbour order, the representation is part of the answer.

Weighted edges with a record

For weighted graphs, int[]{neighbour, weight} works (it is the Java stand-in for C++ pair<int, int>), but e[0] and e[1] are easy to mix up. Since Java 16 a record gives a named, immutable pair in one line, with equals, hashCode and toString generated automatically:

record Edge(int to, int weight) {}

static List<List<Edge>> weighted(int n, int[][] wEdges, boolean directed) {
    List<List<Edge>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : wEdges) {
        adj.get(e[0]).add(new Edge(e[1], e[2]));
        if (!directed) adj.get(e[1]).add(new Edge(e[0], e[2]));
    }
    return adj;
}

A record declared inside a class is implicitly static, so it compiles in the single-file format used here. Code reads naturally, e.to() and e.weight(), and the tests can compare lists of edges with equals because records compare by value: new Edge(0, 5).equals(new Edge(0, 5)) is true, whereas two int[] arrays with equal contents are not equals.

Java traps, demonstrated

remove(int) versus remove(Object). List<Integer> has two remove methods. list.remove(3) with an int argument removes the element at index 3. To remove the value 3 you must pass an object:

static void removeEdge(List<? extends List<Integer>> adj, int u, int v) {
    adj.get(u).remove(Integer.valueOf(v));
    adj.get(v).remove(Integer.valueOf(u));
}

The test removes edge 1-3 from the example and checks that vertex 3’s list goes from [1, 2, 4] to [2, 4]. With remove(v) it would instead have deleted whatever sat at index 1, or thrown IndexOutOfBoundsException for a large vertex number.

One list shared by every vertex. Arrays.fill(adj, new ArrayList<>()) looks like it creates n lists, but new ArrayList<>() is evaluated once and the same object is stored in every slot:

@SuppressWarnings("unchecked")
static List<Integer>[] sharedListBug(int n, int[][] edges) {
    List<Integer>[] adj = new List[n];
    Arrays.fill(adj, new ArrayList<Integer>());
    for (int[] e : edges) {
        adj[e[0]].add(e[1]);
        adj[e[1]].add(e[0]);
    }
    return adj;
}

After adding the single edge 0-1 to a 3-vertex graph, vertex 2, which has no edges, reports two neighbours, and adj[0] == adj[2] is true. Collections.nCopies(n, new ArrayList<>()) has the same problem. Always create the inner lists in a loop.

Which one to use

All of them support a full traversal in O(V + E) except the matrix, which needs O(V^2).

Edge cases and pitfalls