Graph Representation in Java — Adjacency List vs Matrix Trade-offs

Three ways to represent a graph

1. Adjacency matrix

• 2D array V × V
• matrix[u][v] = 1 if edge exists
• Space: O(V²)
• Edge lookup: O(1)
• Neighbor iteration: O(V)

2. Adjacency list

• Map / List of Lists
• Each vertex has a list of neighbors
• Space: O(V + E)
• Edge lookup: O(degree)
• Neighbor iteration: O(degree)

3. Edge list

• List of edges (u, v, weight)
• Space: O(E)
• Used by Kruskal, Bellman-Ford

Trade-offs

Adjacency matrix

Pros

• O(1) edge lookup
• Simple
• Cache-friendly
• Easy for matrix algorithms (Floyd-Warshall)

Cons

• O(V²) space — wasteful for sparse
• O(V) neighbor iteration
• For 1M vertices: 4 TB — infeasible

Use when

• Dense graph (E ~ V²)
• Frequent edge queries
• Small V (≤ 1000)
• Floyd-Warshall, transitive closure

Adjacency list

Pros

• O(V + E) space — efficient for sparse
• O(degree) iteration
• Dynamic vertex/edge add/remove
• Standard for BFS, DFS, Dijkstra

Cons

• O(degree) edge query
• Less cache-friendly
• Memory overhead (object headers, list overhead in Java)

Use when

• Sparse graph (E << V²)
• Real-world graphs (almost always)
• Traversal-heavy
• Large V

Edge list

Pros

• O(E) space — most compact
• Easy to sort by weight
• Natural for file I/O

Cons

• No fast edge lookup
• No fast neighbor iteration
• Convert to list/matrix for BFS/DFS

Use when

• Kruskal MST (sort edges)
• Bellman-Ford (relax all edges)
• Storage / file format

Java implementations

Matrix

int[][] adj = new int[n][n];
adj[u][v] = weight;
adj[v][u] = weight;   // undirected

List

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(u).add(v);

Map-based list (for sparse vertex IDs)

Map<Integer, List<Integer>> adj = new HashMap<>();
adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);

Edge list

List<int[]> edges = new ArrayList<>();
edges.add(new int[]{u, v, weight});

No built-in graph in Java

• Unlike Python's networkx
• Roll your own with Map/List
• Or use JGraphT library

Algorithm complexity depends on representation

BFS/DFS

• List: O(V + E)
• Matrix: O(V²)
• For sparse: huge difference

Dijkstra

• List + heap: O((V + E) log V)
• Matrix + array: O(V²) (better for dense)

Floyd-Warshall

• Requires matrix
• O(V³) time, O(V²) space
• Small V only

Kruskal

• Edge list + union-find: O(E log E)

Prim

• List + heap: O(E log V)
• Matrix + array: O(V²)

Decision guide

• Density: sparse → list; dense → matrix
• Operations: edge query → matrix; traversal → list; edge iteration → edge list
• V size: ≤ 1000 → matrix often fine; ≥ 10K → list
• Memory: budget tight → list
• Algorithm: Floyd-Warshall → matrix; Kruskal → edge list

Real-world default

• Adjacency list
• Most graphs (social networks, web, road, dependencies) are sparse

Advanced: CSR (Compressed Sparse Row)

• Two flat arrays: offsets[V+1], neighbors[E]
• Cache-friendly
• Used in HPC, graph DBs (e.g., Neo4j, Pregel)
• Half the memory of List<List> in Java

Common bugs

1. Always defaulting to one representation

• Match representation to algorithm

2. Forgetting matrix is O(V²) for sparse too

• 1M vertex sparse graph: matrix infeasible, list fine

3. Confusing iteration cost

• Matrix neighbor iteration: O(V) per vertex
• List: O(degree) per vertex

4. Not using adjacency list for Dijkstra

• Matrix version is O(V²); list + heap is O((V+E) log V)
• For sparse: list wins by a lot

5. Storing weights wrong in matrix

• 0 means no edge for unweighted
• For 0-weight edges, use Integer.MAX_VALUE for missing

6. Forgetting bidirectional add for undirected

• adj[u][v] AND adj[v][u]
• Or in list: add to both u's and v's lists

For interviews

Default: adjacency list for most problems Matrix: when V is small and edge queries are frequent Edge list: for Kruskal, Bellman-Ford Mention complexity changes based on representation Mention Java has no built-in graph type

Recommendation: Adjacency list is the default for most graph problems in Java because real-world graphs are sparse (social networks, web, road networks, dependencies) and O(V + E) space scales to billions of edges. Adjacency matrix is preferred when (1) the graph is dense (E ~ V²), (2) edge-existence queries are frequent (O(1) vs O(degree)), (3) V is small (≤ 1000) so O(V²) is manageable, or (4) the algorithm requires it (Floyd-Warshall for all-pairs shortest path). Edge list is the choice for Kruskal's MST (sort by weight) and Bellman-Ford (relax all edges), and is the natural format for file I/O. Java has no built-in graph type — use List> (when vertices are 0..V-1) or Map> (sparse vertex IDs); for weighted edges, use List or a record Edge(int to, int weight). Algorithm complexity changes dramatically with representation: BFS/DFS is O(V + E) on adjacency list but O(V²) on matrix — for sparse graphs, the difference is massive (e.g., 10⁶ vs 10¹² operations for V=10⁶). Dijkstra on list + heap is O((V+E) log V); on matrix + array, it's O(V²) (competitive for dense graphs). For very large graphs, consider CSR (Compressed Sparse Row) — two flat arrays (offsets + neighbors) that's cache-friendly and half the memory of List>. The mental model: matrix = bitmap (fast lookup, dense storage); list = sparse map (efficient for traversal); edge list = compact catalog (good for sorting). Pick based on density, operations, and the algorithm you'll run; default to adjacency list if uncertain.