Graph representation

A graph is a set of nodes (also called vertices) connected by edges. Graphs model almost any relationship: roads between cities, links between web pages, dependencies between software packages, friendships between people. Before you can write a graph algorithm, you need to represent the graph in memory. Two representations dominate — adjacency list and adjacency matrix — and the right choice depends on the density of your graph.

Adjacency list

An adjacency list stores, for each node, the list of nodes it connects to directly. In Python the natural implementation is a dictionary of lists:

# Directed graph: 0→1, 0→2, 1→2
graph = {
    0: [1, 2],
    1: [2],
    2: [],
}

Space: O(V + E), where V is the number of nodes and E the number of edges. Each node appears once as a key; each edge appears once as a list entry. For sparse graphs — where E is much smaller than V² — this is far more compact than a matrix.

Edge lookup: O(degree(v)), where degree(v) is the number of neighbours of v. To check whether an edge (u, v) exists you scan graph[u]. For sparse graphs this is acceptable; for dense ones it is slow.

Iteration over neighbours: O(degree(v)) — simply iterate the list. This is the operation used by BFS and DFS, making adjacency lists the standard choice for traversal algorithms.

Adjacency matrix

An adjacency matrix uses a 2D list indexed by node number. matrix[u][v] = 1 (or a weight) means there is an edge from u to v; 0 means no edge:

# Same graph: 0→1, 0→2, 1→2  (3 nodes)
matrix = [
    [0, 1, 1],   # node 0 connects to 1 and 2
    [0, 0, 1],   # node 1 connects to 2
    [0, 0, 0],   # node 2 connects to nothing
]

Space: O(V²) — always. Even if the graph has only 5 edges and 1000 nodes, the matrix is one million entries. This makes matrices impractical for sparse graphs but acceptable when E approaches V².

Edge lookup: O(1) — matrix[u][v] is a direct index, no scanning needed. For algorithms that query "does edge (u, v) exist?" repeatedly (e.g. Floyd- Warshall all-pairs shortest path), a matrix beats a list.

Directed and undirected graphs

In a directed graph (digraph) each edge has a direction: (u, v) means u points to v, but v does not necessarily point back to u. Web links are directed — a page can link to another without a reciprocal link. To store a directed edge in an adjacency list, add v to graph[u] only.

In an undirected graph edges have no direction: (u, v) and (v, u) are the same edge. Friendship networks are typically undirected. To store an undirected edge, add v to graph[u] and u to graph[v].

def add_undirected_edge(graph, u, v):
    graph[u].append(v)
    graph[v].append(u)

An undirected adjacency list uses twice the entries of a directed one for the same edges, but traversal algorithms that start from any node and need to reach any other node require undirected edges in both directions.

Weighted graphs

A weighted graph assigns a cost or capacity to each edge. Represent weights in an adjacency list by storing (neighbour, weight) tuples instead of plain node ids:

# Weighted directed graph: 0→1 cost 4, 0→2 cost 2, 1→2 cost 1
weighted = {
    0: [(1, 4), (2, 2)],
    1: [(2, 1)],
    2: [],
}

For a weighted adjacency matrix, store the weight directly: matrix[u][v] = weight, and use a sentinel (commonly float('inf')) for absent edges.

Where to go next

Next: BFS and DFS — traversing a graph stored as an adjacency list, using a visited set to avoid re-visiting nodes, and finding connected components.