Graphs and How to Represent Them

A graph models things (vertices/nodes) and the connections between them (edges); the core skill is choosing how to store it.

Vocabulary

• Undirected edge: two-way (friends). Drawn as a plain line.
• Directed edge: one-way, source to target (follows). Drawn as an arrow. All-directed graph = digraph.
• Weight: a number on an edge (cost, distance, capacity). Weighted vs unweighted.
• Degree: edges touching a vertex. Directed splits into in-degree (arrows in) and out-degree (arrows out).
• Path: sequence of vertices linked by edges. Cycle: a path back to its start reusing no edge.
• Acyclic: no cycles. DAG: directed acyclic graph, used for dependencies.
• Neighbors: vertices directly connected (adjacent) to a vertex.

Adjacency list (dict of lists)

• Store each vertex’s neighbor list. Space O(V + E).
• Undirected: each edge appears twice (both endpoints list each other).
• Directed: store only in the source’s list.
• Weighted: use (neighbor, weight) pairs.

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

Adjacency matrix (list of lists)

• Number vertices 0..V-1. matrix[i][j] = 1 means edge i to j (weight for weighted). Space O(V^2).
• Undirected matrix is symmetric: set [i][j] and [j][i].

matrix = [[0,1,1,0],[0,0,0,1],[0,1,0,0],[0,0,0,0]]  # A=0,B=1,C=2,D=3

Trade-offs (V vertices, E edges)

Rule: list for sparse graphs (common) and walking edges; matrix for small/dense graphs or constant edge-existence checks.

Build from an edge list

graph = {}
for u, v in edges:
    graph.setdefault(u, []).append(v)
    graph.setdefault(v, []).append(u)   # drop this line for directed

setdefault(key, []) inserts an empty list if absent, then returns it.

Gotchas

• Undirected: add the reverse edge to both lists, or the walk goes only one way.
• No mutable default args: use def f(graph=None): graph = graph or {}, not graph={}.
• Vertices with no outgoing edges still need an entry (empty list), else KeyError.
• Matrix blows up: 100,000 vertices = 10 billion cells. Sparse and large means list.
• Directed vs undirected: pick before building. Directed [i][j] and [j][i] are independent; undirected must stay equal.