Graph Representations: Edge Lists, Adjacency Lists, and Matrices

“Where can vertex 0 go directly?” and “Is there an edge from 0 to 2?” sound similar, but can require very different scans. An edge list searches all edges, an adjacency list searches vertex 0's own collection, and an adjacency matrix can read a single cell. Choose storage by the questions the algorithm asks repeatedly; the data structures map takes the same approach to choosing containers.

Vertices, edges, and the questions storage must answer

Open Data Structures' graph chapter defines a directed graph as $G=(V,E)$: $V$ is a set of vertices and each edge in $E$ is an ordered pair $(u,v)$, directed from $u$ to $v$. Here $n=|V|$ and $m=|E|$, with integer vertex identifiers 0..n-1.

An undirected edge joins two endpoints; exchanging them leaves the edge unchanged. Directed edges distinguish u→v from v→u. A weighted graph also assigns each edge a weight, such as a length or cost. An unweighted graph records only connectivity. Zero is a valid weight, so a missing edge must be distinguishable from an edge of weight zero.

Storage usually needs to enumerate all vertices and edges, enumerate a vertex's outgoing neighbors, find an edge and its weight, and insert or delete edges. A directed graph may also need incoming neighbors. Keep the vertex set separately: vertices with no incident edges cannot be recovered from edge endpoints alone.

Decide what repeated endpoint pairs mean. A simple graph has neither self-loops nor parallel edges; a representation that allows them can keep a separate record for every edge. A matrix cell holding one weight cannot preserve multiple parallel edges and their identities. The example below allows self-loops but merges repeated input for the same directed pair by minimum weight. It does not preserve all edges of a multigraph.

One graph in three representations

Use vertices 0, 1, 2, 3 and edges 0→1:4, 0→2:0, 1→2:2, and 2→2:5. Vertex 3 is isolated; vertex 2 has a self-loop.

An edge list stores (source, target, weight) records in one array. Adjacency lists keep one collection of outgoing edges per vertex, using (neighbor, weight) for weighted edges. An adjacency matrix uses sources as rows and targets as columns. The textbook uses Boolean cells for edge existence; this example instead stores weights and uses None for a missing edge.

Source / row	Records in the edge list	Adjacency list adj[u]	Matrix row, with columns 0, 1, 2, 3
0	(0,1,4), (0,2,0)	[(1,4), (2,0)]	[None, 4, 0, None]
1	(1,2,2)	[(2,2)]	[None, None, 2, None]
2	(2,2,5)	[(2,5)]	[None, None, 5, None]
3	No record	[]	[None, None, None, None]

The table groups edge-list records by source for comparison; storage remains one array with no source index. With $n=4$ and $m=4$, the edge list stores 4 edge records, the adjacency list has 4 lists containing 4 entries in total, and the matrix allocates $4^2=16$ cells, 4 of which hold edges. These are counts of records and cells, not bytes.

Enumerating vertex 0's outgoing neighbors examines 4 records in the edge list, 2 entries in the adjacency list, or 4 cells in a matrix row. All return [(1,4), (2,0)]. Looking up the weight of 0→2 returns 0; looking up 2→0 returns None. Test matrix edge existence with is not None, rather than the truth value of the weight.

For an undirected graph, adjacency lists normally store each non-loop edge twice: (v,w) in adj[u] and (u,w) in adj[v]. The corresponding matrix cells are equal. An edge list can store an undirected edge once, but neighbor enumeration must check both endpoints. The builder below stores an undirected self-loop as one adjacency entry. Under the graph-theoretic degree convention, it still contributes 2, so list length is not a degree count in that case.

Operation costs depend on containers and conventions

The following comparison concerns edge operations on a fixed vertex set. Edge lists and the inner adjacency lists are unsorted dynamic arrays; matrix cells hold one weight or an absence marker. Indexing, comparing weights, and moving an item are treated as constant-cost operations. Let $d^+(u)$ count the stored outgoing adjacency entries at $u$. Adding 1 includes constant overhead for empty graphs and lists. Time entries are worst-case upper bounds, except for append.

Operation	Edge list	Adjacency list	Adjacency matrix
Total space, including vertices	$\Theta(n+m)$	$\Theta(n+m)$	$\Theta(n^2+n)$
Enumerate all outgoing neighbors of u	$O(m+1)$	$O(d^+(u)+1)$	$O(n+1)$
Look up u→v or its weight	$O(m+1)$	$O(d^+(u)+1)$	$O(1)$
Append an edge without a duplicate check	Amortized $O(1)$	Amortized $O(1)$	$O(1)$ write / overwrite
Find by endpoints and delete an edge	$O(m+1)$	$O(d^+(u)+1)$	$O(1)$

For a nonempty graph, matrix space is usually written as $\Theta(n^2)$; the extra $n$ in the table includes vertex records. Edge-list records alone occupy $\Theta(m)$, but a separate vertex set is needed to retain isolated vertices. See arrays and dynamic arrays for amortized append and shifting on deletion. One resize can still copy the entire array.

Appending without checking duplicates is not the cost of updating a unique edge. If insertion must check endpoints, merge weights, or reject duplicates, an edge list or ordinary adjacency list also pays the lookup cost. Deleting a non-loop edge from an undirected adjacency list must update both ends, taking $O(d(u)+d(v)+1)$. A matrix insertion overwrites the value for an endpoint pair; it cannot append an independent parallel edge.

Replacing each adjacency container with a hash table keyed by neighbor can give expected $O(1)$ lookup, update, and deletion under suitable hashing and controlled load, with resizing requiring its own amortized analysis. Traversal also depends on buckets and capacity; see hash tables. These are different assumptions from the linear lists in the table. If a directed graph stores only outgoing lists, finding incoming neighbors scans all lists in $O(n+m)$ time. A second, reverse adjacency list supports enumeration by incoming-edge count, but every update must maintain both copies.

When $m$ is much smaller than $n^2$, adjacency lists avoid allocating large numbers of empty cells. In dense graphs their space approaches the matrix's order of growth, making direct matrix lookup more attractive. Adding a vertex is a different operation: reallocating and copying a compact matrix can take $O(n^2)$ time, outside the constant-time cell writes in the table.

Building from an edge list: decide what to preserve

The program below uses vertices 0..n-1, a nonnegative integer n, and integer weights. Its input contains 6 records, with weights 7, 4, 4 appearing for 0→1. Merging keeps weight 4 and leaves 4 edges overall. This minimum-weight rule suits parallel edges when only shortest-path costs matter. It discards edge identities and multiplicities, so it cannot count repeated edges or directly combine capacities in a flow network.

Construction has three steps:

1. Check that endpoints belong to the vertex set, then retain the minimum weight under an endpoint-pair key. Preserve endpoint order for a directed graph; put the smaller endpoint first for an undirected graph, merging (0,1) with (1,0).
2. Create an empty adjacency list for every one of the $n$ vertices, then allocate a matrix of missing-edge cells. This gives isolated vertices a place too.
3. Add each retained edge to the adjacency lists and matrix. Add the reverse entry for an undirected non-loop edge; add a self-loop only once.

For $r$ raw records, merging and building adjacency lists takes expected $O(n+r)$ time under expected constant-time hash operations and amortized constant-time array append, with $O(m)$ temporary key storage. This program also builds a matrix, so its total construction time is expected $O(n^2+n+r)$. To retain parallel edges, skip merging and append every record. Deleting a particular edge then calls for an edge ID, and a single-weight matrix must be replaced by a structure that can hold multiple edges.

CPython implements dict as a resizable hash table. These construction bounds also assume fixed-cost key hashing and comparison, with suitable hash distribution; they are not worst-case guarantees for arbitrary inputs.

Runnable example: the same queries on three stores

Save the complete code as graph_representations.py and run python3 graph_representations.py with Python 3.7 or later. Python's dictionary contract guarantees insertion order from 3.7 onward, and updating an existing key does not move it. The edge list therefore prints endpoint pairs in their order of first appearance. The program implements neighbor enumeration and weight lookup separately, checks agreement for every vertex pair in both directed and undirected graphs, and checks reverse duplicates, self-loops, isolated vertices, an empty graph, and an out-of-range endpoint. Query arguments use declared vertices.

def build(n, raw_edges, directed=True):
    best = {}
    for u, v, weight in raw_edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("endpoint outside vertex set")
        key = (u, v) if directed else (min(u, v), max(u, v))
        if key not in best or weight < best[key]:
            best[key] = weight
    edges = [(u, v, weight) for (u, v), weight in best.items()]
    adjacency = [[] for _ in range(n)]
    matrix = [[None] * n for _ in range(n)]
    for u, v, weight in edges:
        adjacency[u].append((v, weight))
        matrix[u][v] = weight
        if not directed and u != v:
            adjacency[v].append((u, weight))
            matrix[v][u] = weight
    return edges, adjacency, matrix


def grid_neighbors(row, column, rows, columns):
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        r, c = row + dr, column + dc
        if 0 <= r < rows and 0 <= c < columns:
            yield r, c


n = 4
raw_edges = [(0, 1, 7), (0, 2, 0), (0, 1, 4),
             (1, 2, 2), (2, 2, 5), (0, 1, 4)]
edges, adjacency, matrix = build(n, raw_edges)
print("edges:", edges)
print("adjacency:", adjacency)
print("matrix:")
for row in matrix:
    print(row)


def edge_neighbors(edges, u, directed=True):
    neighbors = []
    for source, target, weight in edges:
        if source == u:
            neighbors.append((target, weight))
        elif not directed and target == u:
            neighbors.append((source, weight))
    return neighbors


def list_neighbors(adjacency, u):
    return list(adjacency[u])


def matrix_neighbors(matrix, u):
    return [(v, weight) for v, weight in enumerate(matrix[u])
            if weight is not None]


def edge_weight(edges, u, v, directed=True):
    key = (u, v) if directed else (min(u, v), max(u, v))
    return next((w for a, b, w in edges if (a, b) == key), None)


def list_weight(adjacency, u, v):
    return next((w for b, w in adjacency[u] if b == v), None)


def matrix_weight(matrix, u, v):
    return matrix[u][v]


queries = [(0, 2), (2, 0), (2, 2)]
for name, store, neighbors, weight in [
    ("edge-list", edges, edge_neighbors, edge_weight),
    ("adjacency-list", adjacency, list_neighbors, list_weight),
    ("matrix", matrix, matrix_neighbors, matrix_weight),
]:
    print(name, neighbors(store, 0), neighbors(store, 3),
          [weight(store, u, v) for u, v in queries])
    for u in range(n):
        assert sorted(neighbors(store, u)) == sorted(list_neighbors(adjacency, u))
        for v in range(n):
            assert weight(store, u, v) == matrix[u][v]

undirected = build(3, [(0, 1, 7), (1, 0, 4), (1, 1, 0)], directed=False)
assert undirected == (
    [(0, 1, 4), (1, 1, 0)],
    [[(1, 4)], [(0, 4), (1, 0)], []],
    [[None, 4, None], [4, 0, None], [None, None, None]],
)
u_edges, u_adjacency, u_matrix = undirected
for u in range(3):
    assert sorted(edge_neighbors(u_edges, u, directed=False)) == sorted(
        list_neighbors(u_adjacency, u)) == sorted(matrix_neighbors(u_matrix, u))
    for v in range(3):
        assert edge_weight(u_edges, u, v, directed=False) == list_weight(
            u_adjacency, u, v) == matrix_weight(u_matrix, u, v)
assert build(0, []) == ([], [], [])
try:
    build(2, [(0, 2, 1)])
except ValueError:
    pass
else:
    raise AssertionError("invalid endpoint accepted")
print("boundary checks: OK")
print("grid (0, 1):", list(grid_neighbors(0, 1, 2, 3)))

Output:

edges: [(0, 1, 4), (0, 2, 0), (1, 2, 2), (2, 2, 5)]
adjacency: [[(1, 4), (2, 0)], [(2, 2)], [(2, 5)], []]
matrix:
[None, 4, 0, None]
[None, None, 2, None]
[None, None, 5, None]
[None, None, None, None]
edge-list [(1, 4), (2, 0)] [] [0, None, 5]
adjacency-list [(1, 4), (2, 0)] [] [0, None, 5]
matrix [(1, 4), (2, 0)] [] [0, None, 5]
boundary checks: OK
grid (0, 1): [(1, 1), (0, 0), (0, 2)]

Each query row reports vertex 0's outgoing neighbors, vertex 3's outgoing neighbors, and the weights of 0→2, 2→0, and 2→2, in that order. The code copies an adjacency list to return neighbors, so enumeration still reads those entries linearly. The matrix's matrix_weight reads a cell directly.

For undirected edge-list queries, also pass directed=False to match build; the adjacency lists and matrix already contain reverse entries. Neighbor order can differ between representations, so the assertions use sorted to compare neighbors and their weights.

Implicit graphs: grids need not store edges

The program's grid_neighbors treats a two-dimensional grid as a graph. It generates candidates up, down, left, and right, retaining only cells inside the boundary. All cells here are passable; there are no diagonal moves or boundary wraparound. A $2\times3$ grid has 6 vertices, $2(3-1)=4$ horizontal undirected edges, and $(2-1)3=3$ vertical edges: 7 edges in total. Cell (0,1) has neighbors (1,1), (0,0), and (0,2), matching the output.

At most 4 candidates are checked per call, giving $O(1)$ neighbor generation without storing those 7 edges. A regular grid's dimensions take constant space; obstacles also require storage and passability checks. For a grid with $R$ rows and $C$ columns, BFS / DFS still needs visited state and a queue / stack, which can occupy $O(RC)$ space in the worst case. An implicit representation removes edge storage, not search state.

Neighbors can also be computed when edges represent legal operations, such as one move in a puzzle. Include the actual cost of generating and validating each candidate in traversal time; it need not be constant.

Representations assumed by the existing algorithm notes

The graph algorithms map chooses algorithms by problem. This table explains the storage required by this site's code or pseudocode. ODS's graph traversal chapter likewise analyzes BFS / DFS using adjacency lists.

Note	Current representation	Why it fits
BFS / DFS	Mapping from vertices to neighbor lists; unweighted adjacency lists	Each processed vertex enumerates its neighbors, giving $O(n+m)$ for a full traversal. Scanning matrix rows gives $O(n^2)$; scanning an edge list each time gives $O(n(m+1))$.
Dijkstra	(neighbor, weight) adjacency lists with a lazy binary heap	Only the current vertex's outgoing edges are relaxed; weights must be nonnegative. The note gives the general lazy-heap bound $O(n+m\log(m+1))$, with the familiar $O((n+m)\log n)$ form for simple graphs.
Bellman–Ford	Separate n and a reusable (u,v,w) edge list	Every pass relaxes all edges, without needing per-vertex neighbor lookup. Worst-case time is $O(n+nm)$, usually written $O(nm)$ when the edge set is nonempty.
Floyd–Warshall	Distance matrix initialized from an edge list	The triple loop needs arbitrary vertex-pair distances: $O(n^3)$ time and $O(n^2)$ matrix space.
Kruskal	One edge-list record per undirected edge, plus disjoint-set union	Sort by weight, then check whether endpoints share a component. Including initialization, time is $O(n+m\log(m+1))$; no neighbor index is needed.
Prim	Symmetric weighted adjacency lists with a lazy edge heap	Adding a vertex to the tree offers its edges to outside vertices. The whole forest takes $O(n+m\log(m+1))$. The note also lists a matrix with linear selection taking $O(n^2)$.

Traversal bounds here count all vertices and assume constant-cost visited-state and mapping operations. Hash sets and dictionaries require the corresponding expected constant-time assumptions. A search from one start can count reachable vertices and the edges examined, but allocating state arrays for all vertices still adds $O(n)$ initialization. Lazy heaps allow multiple old entries, so keep $\log(m+1)$ for arbitrary multigraphs rather than substituting $\log n$.

An adjacency matrix is also distinct from a distance matrix. Here matrix[2][2]=5 records an actual self-loop of weight 5. Floyd–Warshall first sets distance diagonals to 0 for paths using no edges, then takes the minimum with self-loop weights. It uses infinity for no path and minimum weights for parallel edges.

This site's BFS / DFS functions expect a mapping from vertices to neighbor lists. Convert the example's weighted adjacency lists with graph = {u: [v for v, _ in outgoing] for u, outgoing in enumerate(adjacency)}; empty lists retain isolated vertices. BFS finds paths with the fewest edges. DFS visits reachable vertices but does not guarantee the fewest-edge path. Both ignore weights and cannot compute minimum weighted distances in this example.

My reading · Opened notes are remembered in this browser.