Choosing representation

Count what each representation stores and what each operation costs. The matrix stores n² cells; an undirected adjacency list stores 2m entries plus n list headers; an edge list stores m entries; CSR stores n + 1 + 2m ints. The next items refine these numbers by operation.

Counting cells, not bytes, is the portable way to compare designs: bytes depend on the JVM. For a graph with n = 1000 vertices and m = 3000 edges, the matrix has 1,000,000 cells while the list has 6,000 entries and CSR has 7,001 cells.

1static long[] storedCells(int n, int m) {        // {matrix, list entries, edge list, CSR} for an undirected graph
2    return new long[]{(long) n * n, 2L * m, m, n + 1L + 2L * m};
3}

'Is there an edge from a to b?' is O(1) in a matrix, O(degree of a) in a list and O(m) in an edge list. When the question is asked often on a sparse graph, keep a HashSet of edges encoded as one long (a × n + b) next to the list: O(1) average per test and only m entries. The set must be kept in step with the list when edges are added.

Encode with long, not int: for n above 46,340 the product a × n overflows int. The code shows the list scan and the set lookup side by side; they must always agree.

1class EdgeLookup {
2    private final List<List<Integer>> g = new ArrayList<>();
3    private final Set<Long> set = new HashSet<>();
4    private final int n;
5    EdgeLookup(int n) {
6        this.n = n;
7        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
8    }
9    void addEdge(int a, int b) {                 // directed
10        g.get(a).add(b);
11        set.add((long) a * n + b);               // long: a * n overflows int for large n
12    }
13    boolean viaList(int a, int b) { return g.get(a).contains(b); }      // O(degree)
14    boolean viaSet(int a, int b) { return set.contains((long) a * n + b); }   // O(1) average
15}

Algorithms mostly iterate over neighbours, so measure the cost of that. Visiting every neighbour of every vertex costs O(n²) with a matrix (a full row scan per vertex) and O(n + m) with lists or CSR. On a sparse graph that gap decides everything: for n = 1000 and m = 3000, a full traversal reads 1,000,000 matrix cells against 7,000 list entries.

The code counts steps rather than time, so the comparison is exact and independent of the machine: scanning one row of the matrix always takes n steps, scanning a list takes degree steps.

1static long traversalStepsMatrix(boolean[][] m) {         // visit every neighbour of every vertex
2    long steps = 0;
3    for (int u = 0; u < m.length; u++)
4        for (int v = 0; v < m.length; v++) steps++;       // the whole row is read, edge or not
5    return steps;
6}
7static long traversalStepsList(List<List<Integer>> g) {
8    long steps = g.size();                       // one step per vertex ...
9    for (List<Integer> nb : g) steps += nb.size();       // ... plus one per neighbour entry
10    return steps;
11}

Use the matrix when the graph is dense (m close to n²) or small enough that n² cells fit comfortably, or when you need constant-time edge tests and weights between all pairs (Floyd-Warshall). Use adjacency lists or CSR when the graph is sparse, which is the usual case for large real inputs. A rough rule of thumb: if m is more than a few percent of n², a matrix is competitive; below that, lists win clearly.

The numbers are blunt: a matrix of int for n = 10,000 needs 10,000² × 4 bytes = 400 million bytes of payload, which is 400 MB, whether the graph has 10 edges or 10 million. The function below applies a simple heuristic; treat its threshold as a starting point to be tuned for your data, not as a law.

1static String suggest(int n, long m) {           // a heuristic: matrix only when m is a sizeable fraction of n^2
2    long possible = (long) n * n;
3    return m * 20 >= possible ? "matrix" : "adjacency list";
4}

List<List<Integer>> is convenient but costly: each inner list is an object with its own header and backing array, and every Integer above the cached range (-128 to 127) is a separate heap object of its own, reached through a reference. A graph with a million edges can have millions of small objects, which costs memory and cache misses and gives the garbage collector work. Typical 64-bit JVM figures (16 bytes for an Integer, 4-8 for the reference, plus list headers) are estimates, not measurements; measure your own case.

When performance or memory matters, build an int[][] (one int[] per vertex, sized by degree) or CSR. The conversion below turns the nested lists into jagged arrays: the same neighbour order, no boxing, and far fewer objects. For most contest-sized graphs the lists are fine; reach for arrays when n or m reaches the millions.

1static int[][] toJagged(List<List<Integer>> g) {         // one int[] per vertex, no boxing
2    int[][] out = new int[g.size()][];
3    for (int u = 0; u < g.size(); u++) {
4        List<Integer> nb = g.get(u);
5        out[u] = new int[nb.size()];
6        for (int i = 0; i < out[u].length; i++) out[u][i] = nb.get(i);
7    }
8    return out;
9}
10static int[][] jaggedFromEdges(int n, int[][] edges) {   // undirected, built without boxed lists at all
11    int[] deg = new int[n];
12    for (int[] e : edges) { deg[e[0]]++; deg[e[1]]++; }
13    int[][] g = new int[n][];
14    for (int u = 0; u < n; u++) g[u] = new int[deg[u]];
15    int[] fill = new int[n];
16    for (int[] e : edges) { g[e[0]][fill[e[0]]++] = e[1]; g[e[1]][fill[e[1]]++] = e[0]; }
17    return g;
18}