Graphs: vertices, edges and how to store them

What a graph is

A graph is a set of things and the connections between them. The things are called vertices (or nodes) and the connections are called edges. A tree from Module 7 is a special graph: it is connected and has no loops. A general graph has no root, any vertex can connect to any other, and following edges can bring you back to where you started.

Graphs are everywhere once you look for them. A metro map is a graph: stations are vertices and the tracks between neighbouring stations are edges. A friends network is a graph of people. Flight routes form a graph of airports. The packages your project installs with pip or npm form a graph where "package A needs package B" is an edge.

Words you will hear

• Undirected edge: works both ways, like a two-way road or a friendship. Directed edge: has a direction, like a one-way street or "A follows B" on a social app.
• Weighted edge: carries a number, such as distance in km, travel time or ticket price. Unweighted: every edge counts the same.
• Path: a sequence of vertices where each neighbouring pair is joined by an edge. Cycle: a path that starts and ends at the same vertex.
• Connected: in an undirected graph, every vertex can reach every other. A connected component is one such separate piece; a graph can have many.
• Degree: the number of edges touching a vertex. In a directed graph, in-degree counts edges coming in and out-degree counts edges going out.
• V and E: the usual names for the number of vertices and the number of edges. A sparse graph has few edges (E close to V); a dense graph has many (E close to V²).

Three ways to store a graph

An edge list is just a list of pairs, such as [(0, 1), (1, 2)]. Interview problems usually GIVE you the graph this way, and Kruskal's algorithm (Module 10) uses it directly. But finding the neighbours of one vertex means scanning the whole list.

An adjacency matrix is a V × V grid where matrix[u][v] is 1 (or the weight) when there is an edge from u to v. Checking one edge is O(1), but it always uses V² cells, even when there are few edges. For 100,000 vertices that is 10¹⁰ cells, far too many.

An adjacency list stores, for each vertex, the list of its neighbours. It uses O(V + E) space and lists the neighbours of u in O(degree(u)) time, which is exactly what BFS and DFS need. This is the default choice in interviews.

from collections import defaultdict

edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
adj = defaultdict(list)
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)     # undirected: store both directions
print(dict(adj))
# Output: {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}

When the vertices are numbered 0 to n − 1, a plain list of lists is often simpler: adj = [[] for _ in range(n)]. Every vertex then has an entry, including vertices with no edges, which defaultdict would miss. For a directed graph, append only adj[u].append(v).

n = 4
matrix = [[0] * n for _ in range(n)]
for u, v in [(0, 1), (0, 2), (1, 2), (2, 3)]:
    matrix[u][v] = matrix[v][u] = 1
print(matrix[2][3], matrix[0][3])   # Output: 1 0

Common mistakes

• Adding only one direction for an undirected graph, so half the edges vanish. Fix: append both adj[u].append(v) and adj[v].append(u).
• Building adj = [[]] * n: all n entries are the SAME list. Fix: [[] for _ in range(n)].
• Using an adjacency matrix for a big sparse graph and running out of memory. Fix: use an adjacency list unless V is small (a few thousand at most).
• Missing isolated vertices when building from edges with defaultdict, so loops over adj skip them. Fix: loop over range(n), or create every key first.
• Mixing 1-based labels (people 1 to n) with 0-based lists. Fix: allocate n + 1 slots, or subtract 1 from every label once at the start.
• Assuming the graph is connected. Fix: ask, and when in doubt, loop over every vertex as a possible starting point.