Skip to content
Hari KharelStudy

Graph representation

coreCommon atGoogleMetaAmazonStripeAnthropicRead firstHash mapsArraysPractise in the Sandbox →

A graph is a set of vertices joined by edges. You can store it three ways. An adjacency list gives each vertex its list of neighbors: O(V + E) memory and the fastest neighbor iteration, so it’s the default. An adjacency matrix is a V×V grid: O(1) edge checks but O(V²) memory, only sensible for small or dense graphs. An edge list is just the pairs: compact, and the natural input for sorting edges (Kruskal) or union-find.

The idea in plain words

Section titled “The idea in plain words”

Think of a city’s airports and flights. You could describe them three ways:

  • A departures board per airport (adjacency list): “From SFO you can fly to JFK, SEA, LAX.” To see where you can go next, read one board.
  • A giant mileage chart (adjacency matrix): rows and columns are airports, and each cell says whether there’s a flight. Instant lookup for any pair, but the chart has a cell for every pair of airports in the world, flights or not.
  • The airline’s raw flight log (edge list): “SFO→JFK, JFK→LHR, …”. Easy to write down, easy to sort, slow to ask anything specific.

They hold identical information. They differ in what’s cheap to ask. Graph algorithms mostly ask one thing over and over: “what are the neighbors of v?” That’s why the adjacency list wins most of the time.

Vocabulary you’ll need:

Term Meaning
directed / undirected edges have a direction (follows, depends-on) or not (friendship, roads both ways)
weighted each edge carries a number (distance, cost, capacity)
degree number of edges at a vertex; directed graphs split it into in-degree and out-degree
sparse / dense E much closer to V than to V², or the reverse. Most real graphs are sparse
path, cycle a walk along edges; a cycle returns to its start
connected component a maximal group of vertices that can all reach each other
DAG directed acyclic graph: directed, no cycles (dependencies, schedules)
self-loop, multi-edge an edge from v to itself; two edges between the same pair. Ask whether they’re allowed

See it

Section titled “See it”

Click two vertices to add an edge (click an edge to remove it), or click matrix cells. All three representations update together. Then pick a query and see what each representation has to read to answer it.

Build a graph, see all three representations
click to edit
edges
drawing: click two vertices to add or remove an edge
01234
Click a vertex to start an edge. Click an edge to delete it.
adjacency matrix: click a cell
01234
01234
0
1
1
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
0
0
0
1
0
Undirected: the matrix is symmetric, M[u][v] = M[v][u].
adjacency list
0→12
1→03
2→03
3→124
4→3
edge list
(0,1)(0,2)(1,3)(2,3)(3,4)
answerno
list touches2
matrix touches1
edge list touches5
Edge check: the matrix reads one cell. The list scans u's neighbors (deg(u) = 2; O(1) if each row is a hash set). The edge list scans every edge.
the cell / edge asked aboutuseful workscanned anywayquery vertex

Things to try:

  • Make it directed. The matrix stops being symmetric, and each edge appears in only one list row.
  • Choose list neighbors of u and press complete. The list row and the matrix row now cost the same: dense graphs are where matrices stop losing.
  • Choose visit every edge with only a few edges. The matrix still reads every cell.

When to reach for it

Section titled “When to reach for it”
The problem says… Representation Why
“given a list of edges / pairs / dependencies”, then BFS, DFS, shortest paths adjacency list You’ll iterate neighbors V times; total O(V + E).
vertices are strings or objects (users, airports, packages) hash map → list or set No need to number vertices 0..n−1 first.
“is there an edge between u and v?” asked constantly, V ≤ a few thousand adjacency matrix (or list of hash sets) O(1) per check.
all-pairs shortest paths (Floyd–Warshall), dense graphs, V ≤ ~500 matrix The algorithm is O(V³) over the matrix anyway.
“sort edges by weight”, “process edges in order”, union-find edge list You only ever scan or sort the pairs.
a grid, a puzzle, word transformations implicit graph Don’t build anything: compute neighbors on demand. See grids and state-space search.

How it works

Section titled “How it works”
  1. Make a row for every vertex, even ones with no edges. Isolated vertices are real vertices; forgetting them is a classic bug.
  2. For each edge u→v, append v to u’s row. If the graph is undirected, also append u to v’s row. Every undirected edge is stored twice.
  3. Matrix: set M[u][v] (and M[v][u] if undirected). Weighted graphs store the weight instead of true, with ∞ or null for “no edge”.
  4. Named vertices: use a hash map from name to neighbors instead of an array, and a set for neighbors if you’ll check edges or need to ignore duplicates.
build.py
from collections import defaultdict




def to_adj_list(n: int, edges: list[tuple[int, int]], directed: bool) -> list[list[int]]:
    adj: list[list[int]] = [[] for _ in range(n)]   # 1. one (possibly empty) row per vertex
    for u, v in edges:
        adj[u].append(v)                            # 2. record u -> v
        if not directed:
            adj[v].append(u)                        #    undirected: store both directions
    return adj




def to_matrix(n: int, edges: list[tuple[int, int]], directed: bool) -> list[list[bool]]:
    m = [[False] * n for _ in range(n)]             # V*V cells, even with zero edges
    for u, v in edges:
        m[u][v] = True                              # 3. O(1) "is there an edge?" later
        if not directed:
            m[v][u] = True
    return m




def to_adj_map(edges: list[tuple[str, str]]) -> dict[str, set[str]]:
    """Vertices are names, not 0..n-1: a dict of sets. Sets also make edge checks O(1)."""
    adj: defaultdict[str, set[str]] = defaultdict(set)
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    return dict(adj)




if __name__ == "__main__":
    edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
    assert to_adj_list(5, edges, directed=False) == [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3]]
    assert to_adj_list(5, edges, directed=True) == [[1, 2], [3], [3], [4], []]
    m = to_matrix(5, edges, directed=False)
    assert m[3][1] and m[1][3] and not m[0][4]
    assert to_adj_list(3, [], directed=True) == [[], [], []]   # isolated vertices still exist
    g = to_adj_map([("sfo", "jfk"), ("jfk", "lhr")])
    assert g["jfk"] == {"sfo", "lhr"}
    print("ok")

Two operations come up constantly as building blocks: reversing a directed graph (who points at me?) and counting degrees. Both are one pass over every edge.

transpose.py
def transpose(adj: list[list[int]]) -> list[list[int]]:
    """Reverse every edge of a directed graph: u -> v becomes v -> u. O(V + E)."""
    rev: list[list[int]] = [[] for _ in adj]
    for u, outs in enumerate(adj):
        for v in outs:
            rev[v].append(u)
    return rev




def degrees(adj: list[list[int]]) -> tuple[list[int], list[int]]:
    out_deg = [len(outs) for outs in adj]           # out-degree: free, it's the row length
    in_deg = [0] * len(adj)
    for outs in adj:                                # in-degree: one pass over every edge
        for v in outs:
            in_deg[v] += 1
    return in_deg, out_deg




if __name__ == "__main__":
    adj = [[1, 2], [3], [3], [4], []]               # 0->1, 0->2, 1->3, 2->3, 3->4
    assert transpose(adj) == [[], [0], [0], [1, 2], [3]]
    assert transpose(transpose(adj)) == adj         # reversing twice gives the original back
    assert degrees(adj) == ([0, 1, 1, 2, 1], [2, 1, 1, 1, 0])
    print("ok")

What it costs

Section titled “What it costs”
Adjacency list Adjacency matrix Edge list
memory O(V + E) O(V²) O(E)
add edge O(1) O(1) O(1)
remove edge O(deg u) (O(1) with sets) O(1) O(E)
is u–v an edge? O(deg u) (O(1) with sets) O(1) O(E)
iterate neighbors of u O(deg u) O(V) O(E)
iterate all edges O(V + E) O(V²) O(E)
BFS / DFS total O(V + E) O(V²) O(V·E) unless converted

The matrix’s weakness is memory, and it grows faster than intuition suggests:

Memory: matrix vs list as the graph grows
drag the sliders
Adjacency matrix (1 bit/cell)
12 MB
Adjacency list
469 KB
E ≈ 50,000 edges, density 0.10%. The matrix costs V² no matter how few edges exist; the list costs V + E. Real graphs (road maps, social networks, the web) have small average degree, so at a million vertices the matrix is over a hundred gigabytes even packed as bits, while the list fits in megabytes.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Adjacency sets (dict[node, set[node]]): O(1) edge checks and removals with list-like memory. The best general-purpose interview choice when edges can be removed or duplicated.
  • Both directions for directed graphs. Keep out[u] and in[u] when you need predecessors as often as successors.
  • Implicit graphs. Neighbors come from a rule: the 4 or 8 cells around a grid square, the moves of a knight, every string one edit away. Write a neighbors(state) function instead of building edges up front.
  • Compressed sparse row (CSR). Two flat arrays: offsets[V+1] and targets[E]. Neighbors of u are targets[offsets[u]:offsets[u+1]]. Cache-friendly; what graph libraries use internally.
  • Incidence structures, multigraphs, hypergraphs. Rare in interviews; mention only if asked.
  • Trees are graphs too: connected, acyclic, exactly V − 1 edges. A parent array is a tree representation.

Pitfalls

Section titled “Pitfalls”
  • Adding undirected edges once. Then BFS from one end can’t reach back. Append both directions.
  • Dropping isolated vertices by building the list only from edges. Size the structure from n (or the vertex list), not from the edges.
  • Shared rows in JS: new Array(n).fill([]) puts the same array in every slot. Use Array.from({ length: n }, () => []). Python’s [[]] * n has the same bug.
  • Duplicate edges in a list representation double-count degrees and neighbors. Use sets if the input can repeat edges.
  • Self-loops count twice toward degree in undirected graphs by convention. Decide whether to allow them.
  • Building a matrix for large V. 10⁵ vertices is 10¹⁰ cells. Ask about V before reaching for one.
  • Recursion depth when the representation feeds DFS on a long path graph. See DFS.

In the interview

Section titled “In the interview”
  • First ask: directed or undirected? weighted? how many vertices and edges? can there be self-loops or duplicate edges? are vertices numbered or named?
  • Say the choice and why: “Adjacency list as a dict of sets: O(V + E) memory, O(1) edge checks, and the vertices are strings.”
  • Give complexities in V and E, not n.
  • Expect follow-ups: “What if the graph doesn’t fit in memory?” (edge list on disk, sort by source, stream; or partition by vertex), “What if edges are added and removed constantly?” (sets), “What if you need predecessors too?” (keep the reverse graph).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
A social graph has 10 million users and each follows about 200 others. Which representation, and roughly how big?
Check yourself
pick one
BFS visits every vertex and, for each one, all its neighbors. What does BFS cost on an adjacency matrix?
Check yourself
pick one
In TypeScript, `const adj = new Array(3).fill([]); adj[0].push(1);` What is `adj[2]`?

Practice on your own

Section titled “Practice on your own”

These are classic textbook exercises, not gym questions:

  • Convert an adjacency matrix to an adjacency list and back; check you get the original.
  • Find the “town judge”: the person everyone trusts who trusts nobody (in-degree n−1, out-degree 0).
  • Find the center of a star graph from its edge list.
  • Clone a connected undirected graph given one node, using a map from old node to new node.
  • Is there a path from s to t? Solve it once with BFS on an adjacency list and once with union-find on the edge list.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Breadth-first searchThe first thing you run on an adjacency list.
Depth-first searchComponents, cycles, and orderings.
Topological sortIn-degrees and DAGs in action.
Union-findConnectivity straight from an edge list.