Adjacency List / MatrixAdjacency lists and matrices

01Why it exists

Reach for it when you see:Who connects to whom, what the neighbours are, directed or undirected, weighted or not, sparse or dense, how big V and E are.

02The core idea

A graph is made of vertices (nodes) and edges. Edges may have a direction (in a directed graph, A → B says nothing about B → A) or not, and they may carry a weight — a distance, a cost — or not. What a problem usually hands you is an edge list: a pile of (u, v) or (u, v, w) tuples. That is the rawest format, and algorithms almost never run on it directly, so your first step is always to convert it into one of the two representations below.

The adjacency list maps each node to a list of its neighbours. It takes O(V + E) space, and listing u's neighbours means reading one row — which is the single most common thing traversal algorithms do. The downside is that asking "is there an edge between u and v?" means scanning u's row. Each edge of an undirected graph is recorded at both ends, so the rows add up to 2E entries in total.

The adjacency matrix is a V × V table where matrix[u][v] holds the edge's weight, or 1. Asking whether an edge exists is O(1), but listing a node's neighbours means scanning a whole row at O(V), and the space is always O(V²) no matter how few edges there really are. It only pays off on a dense graph, or when V is small.

How to choose: look at E against V². For a sparse graph — a social network, a map, the web's link structure, anything where E ≪ V² — use a list. For a dense graph, or when you need an O(1) adjacency test, use a matrix. In practice it is a list more than nine times out of ten. When the nodes are the integers 0..n−1, use list[list[int]]; when they are strings or objects, use dict[node, list].

03The algorithm

1. 1Read the problem carefully: directed or undirected, weighted or not, whether the nodes are integers or something else, and how big V and E are.
2. 2Build an adjacency list by default: adj = [[] for _ in range(n)] or defaultdict(list).
3. 3For each edge (u, v), do adj[u].append(v), plus adj[v].append(u) if the graph is undirected. When there are weights, store (v, w).
4. 4Only switch to a matrix, [[0] * n for _ in range(n)], when E approaches V² or you need an O(1) adjacency test.
5. 5Grid problems do not need an explicit graph: treat (row, col) as the node, the four directions as the edges, and walk the array directly.

04Interactive demo

The same graph in both representations. Toggle directed or undirected and weighted or unweighted, then click any node to see which row of the list and which row of the matrix light up as its neighbours. Note how many cells each representation uses.

05Code

Building an adjacency list and an adjacency matrix from an edge list, each handling the directed, undirected and weighted cases. At the end is the form you will see most often, with integer nodes — it is what the rest of the graph lessons use.

from collections import defaultdict

# Edge list: the rawest input format, and usually how a problem hands you the graph
edges = [("A", "B", 4), ("A", "D", 1), ("B", "C", 2), ("B", "E", 5), ("D", "E", 3), ("E", "C", 1)]


# Adjacency list: each node maps to its neighbours (with weights). O(V + E) space
def build_list(edges, directed=False):
    adj = defaultdict(list)
    for u, v, w in edges:
        adj[u].append((v, w))
        if not directed:
            adj[v].append((u, w))       # an undirected edge is recorded on both ends
    return adj

adj = build_list(edges)
for v, w in adj["B"]:                    # walk B's neighbours: only edges that actually exist
    print(v, w)


# Adjacency matrix: a V×V table where matrix[i][j] is the weight (0 or None means no edge). O(V²) space
def build_matrix(nodes, edges, directed=False):
    idx = {n: i for i, n in enumerate(nodes)}
    n = len(nodes)
    m = [[0] * n for _ in range(n)]
    for u, v, w in edges:
        m[idx[u]][idx[v]] = w
        if not directed:
            m[idx[v]][idx[u]] = w
    return m

m = build_matrix(["A", "B", "C", "D", "E"], edges)
print(m[1][2] != 0)                      # are B and C adjacent? O(1)


# The most common form when nodes are the integers 0..n-1
n = 5
adj_int = [[] for _ in range(n)]
for u, v in [(0, 1), (0, 3), (1, 2), (1, 4), (3, 4), (4, 2)]:
    adj_int[u].append(v)
    adj_int[v].append(u)

06Practice

• LeetCode 1557Minimum Number of Vertices to Reach All Nodes (count in-degrees)Medium
• LeetCode 997Find the Town Judge (in-degree and out-degree)Easy
• LeetCode 133Clone GraphMedium
• LeetCode 1971Find if Path Exists in Graph (build the graph, then traverse)Easy
• LeetCode 1436Destination CityEasy