Graph Representation

To run algorithms on graphs, we must choose a concrete way to store:

  • The set of vertices.
  • The set of edges (and optionally their weights or directions).

Two primary representations are:

  • Adjacency list
  • Adjacency matrix

Each has its strengths and weaknesses.

Adjacency List

An adjacency list stores, for each vertex, the list of neighbors it connects to.

Example (undirected, unweighted):

  • Vertices: 0, 1, 2, 3
  • Edges: (0,1), (0,2), (1,2), (2,3)

Adjacency list (0‑based):

  • adj[0] = [1, 2]
  • adj[1] = [0, 2]
  • adj[2] = [0, 1, 3]
  • adj[3] = [2]

In code:

Java
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
    adj.add(new ArrayList<>());
}
// add undirected edge u-v
adj.get(u).add(v);
adj.get(v).add(u);

Pros:

  • Space: O(n + m) for n vertices and m edges.
  • Great for sparse graphs (m much smaller than n²).
  • Easy to iterate over neighbors of a vertex.

Cons:

  • Checking if an edge (u, v) exists may be O(deg(u)) (scan adjacency list).

Adjacency Matrix

An adjacency matrix is an n x n matrix M where:

  • M[u][v] is:
    • 1 or true if there is an edge from u to v.
    • A weight if the graph is weighted.
    • 0 or false / special value if no edge.

Example (undirected, unweighted):

Plain text
   0 1 2 3
0  0 1 1 0
1  1 0 1 0
2  1 1 0 1
3  0 0 1 0

In code:

Java
int[][] matrix = new int[n][n]; // 0 = no edge, 1 = edge
matrix[u][v] = matrix[v][u] = 1; // undirected

Pros:

  • O(1) check for existence of edge (u, v).
  • Simple representation, especially for dense graphs.

Cons:

  • Space: O(n²) regardless of number of edges.
  • Iterating over neighbors of u is O(n) (scan row u).

When to Use Which

Use adjacency lists when:

  • Graph is sparse (m close to O(n) or O(n log n)).
  • You need to efficiently iterate over neighbors (DFS, BFS, Dijkstra).

Use adjacency matrices when:

  • Graph is dense (m close to O(n²)).
  • You need very fast edge existence checks.
  • n is small enough that O(n²) memory is acceptable.

In interview problems, adjacency lists are the default unless an adjacency matrix is explicitly given or strongly implied.