Graphs in Python

Graph Representation Lab

One graph, stored three ways. Step through each operation and watch the drawing, the matrix and the adjacency list change together, one line of Python at a time.

V and E: what a graph is

n = 5          # vertices 0, 1, 2, 3, 4
edge_list = [(0, 1), (0, 2), (0, 3),
             (1, 3), (2, 4), (3, 4)]
is_directed = True

V is the set of vertices (nodes), here numbered 0 to n - 1. E is the set of edges, each a pair (u, v). Directed: the edge goes one way, u → v. Undirected: it works both ways.

Edge list: just the pairs

edge_list = []
def add_edge(u, v):
    edge_list.append((u, v))

Exactly what you read from input. Smallest to store, O(E), but nothing is indexed by vertex, so most questions mean scanning every pair.

Adjacency matrix: a V × V grid

matrix = [[0] * n for _ in range(n)]
def add_edge(u, v, is_directed=True):
    matrix[u][v] = 1
    if not is_directed:
        matrix[v][u] = 1

matrix[u][v] is 1 when there is an edge from u to v. Any lookup is one index, O(1), but the grid costs V² cells even when most are 0.

Adjacency list: each vertex lists its neighbours

from collections import defaultdict
adj = defaultdict(list)
def add_edge(u, v, is_directed=True):
    adj[u].append(v)
    if not is_directed:
        adj[v].append(u)

adj[u] holds only the vertices u connects to. Space O(V + E), and walking a vertex's neighbours costs exactly its degree.

an edgedashed = stored in some structures, not all (half-built or half-removed)touched by the highlighted linebeing checked, or already checked by a loop1 edge 0 no edge

edge_list

Drawing

Adjacency matrix matrix[u][v]

Adjacency list adj[u]

Tip: the ← and → keys step too.

Cost of each operation

Operation	Edge list	Adjacency matrix	Adjacency list
Space	O(E)	O(V²)	O(V + E)
Add an edge	O(1)	O(1)	O(1)
Remove an edge	O(E)	O(1)	O(deg(u))
has_edge(u, v)	O(E)	O(1)	O(deg(u)); O(1) average with sets
Iterate neighbours of u	O(E)	O(V)	O(deg(u))
Iterate every edge	O(E)	O(V²)	O(V + E)
Add a vertex	O(1)	O(V) growing Python lists in place; O(V²) if you reallocate	O(1)

Which one should I use?

Default: adjacency list

Most real graphs are sparse: E is far smaller than V². Roads, friendships, imports between files. BFS, DFS and Dijkstra all walk neighbours, and the list does that in O(deg(u)), so a full traversal is O(V + E).

Matrix: small or dense graphs

Use it when E is close to V², when V is small, or when you ask has_edge constantly. Floyd–Warshall works directly on a matrix. Watch the memory: V = 10,000 means 100,000,000 cells. As a Python list of lists that is about 800 MB of references; even 1 byte per cell is 100 MB.

Edge list: algorithms that want edges

Keep the pairs when you process edges rather than vertices. Kruskal's algorithm sorts them by weight; Bellman–Ford loops over all of them each round. It is also the usual input format, so you often convert it once at the start.

Undirected graphs: the matrix is symmetric, matrix[u][v] == matrix[v][u], and every edge appears twice in the adjacency list (once in each endpoint's list, 2E entries in total). The edge list stores it once.