Graph Representations

A graph is the simplest structure that captures relationships. Two ingredients: nodes (things) and edges (connections between things). That is it. Friendships on a social network, hyperlinks between web pages, flights between airports — all graphs.

The question this lesson answers is not what a graph is but how to store one so your code can work with it efficiently.

The vocabulary you need

Directed vs undirected. A directed graph (digraph) has edges with direction — an arrow from A to B does not imply one from B to A. Twitter follows are directed. Undirected graphs treat edges as symmetric — Facebook friendships go both ways.

Weighted vs unweighted. Edges can carry a number (distance, cost, capacity). The representations below work for both; weighted versions just store a number alongside each neighbor instead of a plain 1.

Degree. For a node in an undirected graph, degree is the count of its edges. In a directed graph you distinguish in-degree (edges arriving) from out-degree (edges leaving).

Sparse vs dense. A complete graph (every pair of nodes connected) has V(V−1)/2 edges for V nodes — that is O(V²). Most real graphs are sparse: a social network of a million people does not have a trillion friendships. The choice of representation depends heavily on how sparse the graph is.

Click any edge in the diagram above. The same connection lights up in the adjacency list and the matrix simultaneously. Toggle directed/undirected to see how the matrix symmetry changes.

Adjacency list

The most common representation. Adjacency means “directly connected by an edge” — an adjacency list records, for each node, exactly which nodes it is adjacent to. Each node maps to the list of its neighbors.

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["D"],
    "D": [],
    "E": [],
}

Space: O(V + E). You store one entry per node (the V part — even nodes with no edges need a key in the dict) and one entry per directed edge (the E part). For an undirected graph each edge appears twice (once in each direction), so it is O(V + 2E) = O(V + E).

Iterate all neighbors of a node: O(degree) — just walk the list. This is the operation you do constantly in graph traversals (BFS, DFS, Dijkstra).

Check if edge (u, v) exists: O(degree(u)) in a plain list. If you swap the inner list for a set you get O(1), at a small overhead cost.

Add an edge: O(1) amortized (append to the list).

Adjacency matrix

A V×V 2D array. matrix[i][j] = 1 means there is an edge from node i to node j.

#     A  B  C  D  E
# A [ 0, 1, 1, 0, 0 ]
# B [ 0, 0, 0, 1, 1 ]
# C [ 0, 0, 0, 1, 0 ]
# D [ 0, 0, 0, 0, 0 ]
# E [ 0, 0, 0, 0, 0 ]

matrix = [
    [0, 1, 1, 0, 0],  # A
    [0, 0, 0, 1, 1],  # B
    [0, 0, 0, 1, 0],  # C
    [0, 0, 0, 0, 0],  # D
    [0, 0, 0, 0, 0],  # E
]

For an undirected graph the matrix is symmetric: matrix[i][j] == matrix[j][i] always.

Space: O(V²). Always. Whether you have 6 edges or 600, you allocate V² cells. With V = 10,000 nodes that is 100 million cells — about 400 MB for 32-bit integers.

Check if edge (u, v) exists: O(1). A single array lookup. This is the matrix’s killer advantage.

Iterate all neighbors of a node: O(V). You must scan the entire row even if most entries are 0. That is painful for sparse graphs.

Picking the right one

The rule of thumb: start with an adjacency list. Almost every graph you encounter in practice — web graphs, social graphs, package dependency graphs, road networks — is sparse. The memory penalty of O(V²) is prohibitive, and iterating neighbors is O(V) instead of O(degree).

Use a matrix when V is small, the graph is dense, and O(1) edge existence checks are the dominant operation.

Build it yourself

Run this code. It constructs an adjacency-list representation from an edge list and then prints each node’s neighbors.

Quick check