Graph Representations
There are two common ways to represent graphs in Java: adjacency matrix and adjacency list. The choice affects memory and performance.
1. Adjacency Matrix
A 2D array where cell (i,j) indicates an edge from i to j. Good for dense graphs (many edges), but uses O(V²) space.
int[][] adjMatrix = new int[V][V];
adjMatrix[u][v] = 1; // edge u->v (for weighted, store weight)
int edge = adjMatrix[u][v];
2. Adjacency List
Array of lists, each list contains neighbors of a vertex. Efficient for sparse graphs. Uses O(V+E) space.
List[] adjList = new ArrayList[V];
for (int i = 0; i < V; i++) adjList[i] = new ArrayList<>();
adjList[u].add(v); // edge u->v
for (int neighbor : adjList[u]) { ... }
For weighted graphs, store objects with node and weight, or use a Map.
Two Minute Drill
- Adjacency matrix: O(V²) space, O(1) edge lookup.
- Adjacency list: O(V+E) space, O(degree) edge iteration.
- Choose based on graph density and operations.
- List representation is more common in Java.
Need more clarification?
Drop us an email at career@quipoinfotech.com