Graph Representations

A graph is the simplest structure for capturing relationships: just nodes (things) and edges (connections between them). Friendships on a social network, links between web pages, flights between airports — every one of these is a graph.

The question this lesson answers is not what a graph is, but how to store one so your code can work with it without drowning in memory or time.

A few words first

An edge can be directed (an arrow from A to B that does not imply B to A — a Twitter follow) or undirected (a mutual link — a Facebook friendship). It can also be weighted, carrying a number like distance or cost. A node’s degree is how many edges touch it. And graphs are usually sparse: a social network of a million people has nowhere near the trillion friendships a fully-connected graph would hold. That sparseness is the single fact that decides which representation to use.

Here is the small undirected graph we will store two ways:

Adjacency list

The everyday choice. For each node, you keep the list of its neighbours:

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

This costs O(V + E) space — one entry per node, plus one per edge end. Walking all of a node’s neighbours is O(degree), which is exactly what graph traversals do over and over. Checking whether a specific edge exists is O(degree) with a list (or O(1) if you store neighbours in a set). Adding an edge is O(1).

Adjacency matrix

The other choice is a V×V grid where cell [i][j] = 1 marks an edge from node i to node j. For an undirected graph it is symmetric:

     A  B  C  D  E
  A  0  1  1  0  0
  B  1  0  0  1  1
  C  1  0  0  1  0
  D  0  1  1  0  1
  E  0  1  0  1  0

The matrix’s one superpower is O(1) edge lookup — “is there an edge from C to D?” is a single cell read. But it always costs O(V²) space, whether the graph has six edges or six million, and walking a node’s neighbours means scanning a whole row of mostly zeros — O(V). With 10,000 nodes that is 100 million cells, regardless of how few edges you actually have.

Which one?

The rule of thumb is short: start with an adjacency list. Almost every real graph — web, social, road, dependency — is sparse, so the matrix’s O(V²) is a memory tax you do not want to pay. Build one from an edge list and the cost difference shows up immediately:

def build_adj_list(edges):
    graph = {}
    for u, v in edges:
        graph.setdefault(u, []).append(v)
        graph.setdefault(v, []).append(u)      # undirected: store both ends
    return graph

edges = [("A","B"), ("A","C"), ("B","D"), ("B","E"), ("C","D"), ("D","E")]
graph = build_adj_list(edges)

V, E = len(graph), len(edges)
print("V =", V, " E =", E)
print("adjacency list  : V + E =", V + E, "entries")
print("matrix would be : V × V =", V * V, "cells")

V = 5  E = 6
adjacency list  : V + E = 11 entries
matrix would be : V × V = 25 cells

Eleven against twenty-five looks minor here. Scale to a million sparse nodes and it becomes the gap between megabytes and terabytes.

Practice