Representing a Graph
Adjacency list vs. adjacency matrix, directed vs. undirected, weighted vs. unweighted - and how to model a problem as a graph in the first place.
On this page
A tree is a special graph - one with no cycles and a single path between any two nodes. A graph drops those restrictions: any node can connect to any other, cycles are allowed, and there may be many paths or none. Graphs model roads, social networks, task dependencies, web links - and the first skill is knowing how to represent one in code.
Nodes, edges, and the four axes
A graph is a set of nodes (vertices) connected by edges. Graphs vary along a few axes, and recognizing which kind you have shapes the whole solution:
- Directed vs. undirected - do edges have a direction (a follows b) or go both ways (a is friends with b)?
- Weighted vs. unweighted - do edges carry a cost (distance, time) or are they all equal?
- Cyclic vs. acyclic - can you follow edges back to where you started?
- Connected vs. disconnected - is every node reachable, or are there separate islands?
Adjacency list vs. adjacency matrix
Two representations dominate. An adjacency list stores, for each node, a list of its neighbors - compact and the default for most problems:
// adjacency list: node → its neighbors. Ideal for sparse graphs.
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.computeIfAbsent(a, k -> new ArrayList<>()).add(b); // edge a → b
// for an undirected graph, also add b → aAn adjacency matrix is an n×n grid where matrix[i][j] marks (or weights) an edge from i to j -
O(1) edge lookup, but O(n²) space:
int[][] matrix = new int[n][n];
matrix[a][b] = 1; // or the weight| Adjacency list | Adjacency matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) |
| "Is there an edge a→b?" | O(degree) | O(1) |
| Iterate a node's neighbors | O(degree) | O(V) |
| Best for | sparse graphs (most problems) | dense graphs, or frequent edge checks |
Real-world graphs are usually sparse (few edges relative to nodes²), so the adjacency list is the default choice in interviews.
The hard part is often modeling
Many problems don't say 'graph' but are one: cities and flights, courses and prerequisites, words that differ by one letter, cells in a grid. The insight is recognizing the nodes and edges. Ask: what are the things (nodes), and what connects them (edges)? Once you see the graph, BFS/DFS solve it.
An adjacency list is like listing, for each city, the roads leaving it: 'from Denver you can reach Boulder, Aurora, Golden.' Compact, and perfect when you want to explore outward from a city. An adjacency matrix is the distance chart printed in an atlas - a big grid with every city on both axes and the distance in each cell. Looking up 'Denver to Miami' is instant, but the chart is mostly empty cells for cities with no direct road, wasting space. Sparse road networks favor the neighbor lists; a fully connected set of hubs favors the chart.
You're given a list of courses and prerequisite pairs like "to take course 3, first take course 1." You must determine a valid order to take all courses. Identify the nodes, the edges (and their direction), and what kind of graph this is - then name the property that makes a valid order impossible.
Why is an adjacency list usually preferred over an adjacency matrix in interviews?
Key takeaways
- A graph is nodes connected by edges, generalizing trees to allow cycles, multiple paths, and disconnection.
- Classify by four axes: directed/undirected, weighted/unweighted, cyclic/acyclic, connected/disconnected.
- Adjacency list (node → neighbors) is O(V + E) space and the default for sparse graphs; adjacency matrix is O(V^2) but gives O(1) edge checks.
- Most interview graphs are sparse, so use the adjacency list.
- The hard part is often modeling: identify the nodes (things) and edges (connections) hidden in the problem.