Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Adjacency Matrix
For a graph with vertices, the adjacency matrix is an matrix with if there is an edge between and , and otherwise.
Properties:
- diagonal entries are if no vertex has a self-loop
- the matrix of an undirected graph is symmetric,
- it always has entries, so the space complexity is

For a directed graph, means an edge from to . At least one pair has but , so the matrix is not symmetric, e.g. is an edge but is not.

Adjacency Lists
An adjacency list keeps, for each vertex, a list of its neighbours (for a digraph, only the vertices it has an out-edge to). In Python this is a dictionary:
graph = {
1: [2, 5],
2: [1, 3, 4],
3: [2, 5],
4: [2],
5: [1, 3],
}
In an undirected graph each edge appears twice: in 's list and in 's list. With vertices and edges there are list heads and list nodes, so the space complexity is .
Weighted Graphs
A cost adjacency matrix stores = cost of edge , e.g. the cost from to is .

As a Python dictionary, each vertex maps to another dictionary of neighbour and weight. For an undirected graph both directions must be listed:
graph = {
1: {2: 58, 5: 55},
2: {1: 58, 3: 20, 4: 89},
3: {2: 20, 5: 23},
4: {2: 89},
5: {1: 55, 3: 23},
}Matrix or Lists
| Adjacency matrix | Adjacency lists | |
|---|---|---|
| Space | ||
| Dense graph () | about equally efficient | about equally efficient |
| Sparse graph () | many wasted zeros | more efficient |
| Check one edge | scan a list |
Adjacency lists are usually the better computational choice, while matrices can be more intuitive. A representation is only a storage format: an undirected graph has the same adjacency lists as a certain directed graph, so the lists alone do not tell you whether the graph is directed. Converting lists into a matrix is a common exam task:
def adjlist_to_matrix(adj, n): # vertices 1..n
A = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in adj[i]:
A[i][j] = 1
return AThe costs of graph operations in each format are listed in Big-O Summary Tables.