At the end of the previous module we left a deliberate debt: five lessons talking about routes, segments and "edges" — the ants' pheromone literally lived on them — without formally defining what that structure is. The time has come to settle it. In this lesson we define rigorously what a graph is, we learn the two classic ways to represent one in memory (adjacency matrix and adjacency list), we analyze when each one pays off, and we introduce the canonical graph of Rutalia's urban network, which will be our proving ground throughout module 3, just as the TSP instance was in module 2. Choosing the representation well is not a cosmetic detail: it determines the complexity of every algorithm we will see afterwards.

1. Formal definition: vertices, edges and variants
2. Essential vocabulary: degree, paths, cycles and connectivity
3. The canonical graph of Rutalia's urban network
4. Adjacency matrix
5. Adjacency list
6. Comparison: when to use each representation
7. Implicit graphs: the grid from 01-03 was a graph all along
8. A note on networkx

A graph is a pair G = (V, E) where:

• V is a finite set of vertices or nodes. In Rutalia: intersections, squares, city zones, delivery points.
• E is a set of edges, each connecting a pair of vertices. In Rutalia: drivable street segments between two points.

On top of this minimal base we build the variants we will need:

• Undirected graph: edges are unordered pairs {u, v}. If you can go from Market Square to the Warehouse, you can also go the other way. A two-way street.
• Directed graph (digraph): edges are ordered pairs (u, v); the relation goes from u to v. A one-way street. Task dependencies (03-02) and flow networks (03-05) are directed by nature.
• Weighted graph: each edge carries an associated weight w(u, v): travel minutes, kilometers, cost, capacity. Without weights, every street "costs" the same; with weights, the city becomes realistic.

Size notation we will use throughout: |V| = n (number of nodes) and |E| = m (number of edges). In an undirected graph with no repeated edges, m can reach at most n(n−1)/2, that is, O(n²). A graph with m close to n² is called dense; with m close to n, sparse. Real street networks are very sparse: each intersection connects to 3 or 4 streets, not to thousands.

• Adjacency: u and v are adjacent (neighbors) if the edge {u, v} exists.
• Degree of a vertex, deg(v): the number of edges incident to it. In directed graphs it splits into in-degree (incoming edges) and out-degree (outgoing edges). A useful property for catching bugs: in an undirected graph, the sum of all degrees is exactly 2m (each edge contributes 2).
• Path: a sequence of vertices v₀, v₁, …, vₖ where each consecutive pair is joined by an edge. Its length is the number of edges (k) or, in weighted graphs, the sum of the weights. A path is simple if it repeats no vertices.
• Cycle: a path that starts and ends at the same vertex without repeating edges. A directed graph with no cycles is called a DAG (Directed Acyclic Graph); DAGs will be key to the topological sort in 03-02.
• Connected graph (undirected): there is a path between every pair of vertices. If not, the graph decomposes into connected components — pieces of the city cut off from one another. We already computed components in 01-04 with union-find; in 03-02 we will do it with search as well and compare.
• Tree: a connected graph with no cycles. It has exactly n−1 edges. The spanning trees of 03-04 are exactly this: the minimal skeleton that keeps everything connected.

Just as module 2 fixed its canonical TSP instance (9 stops + depot, optimum 35.22 km), this module fixes its canonical urban network: 9 city zones and 15 two-way street segments, weighted in van minutes. All data is fictional.

Deliberate details we will exploit in the coming lessons:

• The edge ALM–CEN with weight 12 is the big avenue running straight to the Historic Center: a single segment, but congested. A preview: going through the Market (ALM→MER→CEN = 4+5 = 9 min) is faster than the "straight line". This tension between fewer segments and fewer minutes is exactly the difference between BFS (03-02) and Dijkstra (03-03).
• The Industrial Park (IND) has only 2 connections (degree 2): it is the most fragile zone in the face of street closures.
• The Historic Center (CEN) is the node of highest degree (5): the heart of the network.

Quick check of the degree property: 4+3+3+4+3+5+2+4+2 = 30 = 2·15 ✓.

The adjacency matrix is an n×n table where cell [i][j] holds the weight of edge i→j (or a special value — 0, None, inf — if it doesn't exist). In an undirected graph, the matrix is symmetric: [i][j] == [j][i].

Points worth understanding line by line:

• IDX translates readable names ("ALM") into matrix indices (0). It is the same dict→index trick we used with hash tables in 01-04.
• [[math.inf] * n for _ in range(n)] creates n independent rows. Beware the classic bug [[inf]*n]*n, which creates n references to the same row (we come back to it in Common Mistakes).
• Checking whether an edge exists is a direct access: O(1). That is the matrix's great virtue.
• The price: O(n²) memory even if the graph has few edges, and iterating over a node's neighbors forces you to scan its entire row: O(n).

The adjacency list stores, for each node, only the list of its neighbors (with the weight). In Python the most natural form is a dictionary of dictionaries:

Observations:

• defaultdict(dict) saves us from checking "does the key already exist?" on every insertion; at the end we convert it to a plain dict to freeze the structure.
• We use {neighbor: weight} instead of a list of tuples [(neighbor, weight), ...] because that way the query "is there an edge u–v?" is also O(1) expected thanks to hashing (a seed from 01-04). With lists of tuples it would be O(degree).
• Memory: O(n + m) — exactly proportional to what exists. For Rutalia's network it makes no difference (9 nodes), but for the full street map of a big city (hundreds of thousands of intersections, average degree ~3) the matrix would be unworkable: 10⁵ nodes ⇒ 10¹⁰ cells.

Practical rule:

• Adjacency list: the default choice, and the ideal one for sparse graphs such as road networks. Almost every algorithm in the module (BFS, DFS, Dijkstra, Kruskal, Prim, flow) uses it because their dominant work is "iterate over neighbors".
• Matrix: wins when the graph is dense, when n is small, or when the algorithm constantly queries weights between arbitrary pairs. Floyd-Warshall (03-03) works directly on the matrix — in fact, it is dynamic programming over it.

Does the matrix ring a bell? In 02-02, the canonical TSP instance relied on a distance matrix between the 10 stops. That was the adjacency matrix of a complete graph (everything connected to everything): maximally dense, which is exactly why the matrix was the right choice there.

You don't always need to build the structure in memory. An implicit graph is one whose nodes and edges are computed on demand through a neighbors(state) function.

The example is in this very course: in 01-03 we solved the minimum cost to cross the city grid with dynamic programming. Each cell (i, j) was a node; the allowed moves (right, down) were directed edges weighted by the cost of the destination cell. We never stored "the graph": we generated it as we moved.

This idea scales to enormous spaces (puzzle states, fleet configurations) where materializing the graph would be impossible; the state-space search of 04-03 lives off it. The important part: every algorithm in this module only needs to know how to ask for "the neighbors of u" — it doesn't care whether they come from a dict or from a function.

In a professional setting you will rarely reimplement these structures: the networkx library offers directed/undirected/weighted graphs with dozens of battle-tested algorithms.

In this course we implement the essentials by hand — it is the only way to truly understand each algorithm's costs and failure modes — and we will use libraries (networkx, scipy) for verification or as the final tool, just as we did with scipy.optimize.linprog in 02-01.

• Creating the matrix with [[inf] * n] * n: the outer multiplication duplicates references to the same list; writing matrix[0][3] changes "every row". Always use the comprehension [[inf] * n for _ in range(n)].
• Forgetting the reverse edge in undirected graphs: if you only insert graph[u][v], your "two-way street" becomes one-way and BFS/Dijkstra will produce nonsense. Centralize construction in a function (like build_graph) and never insert edges by hand.
• Invisible isolated nodes: with defaultdict, a node without edges never appears as a key. If your problem allows disconnected zones, initialize every key explicitly or keep the set V separately.
• Confusing dense and sparse when choosing the structure: before coding, estimate m against n². Road network ⇒ sparse ⇒ list. All-pairs distance matrix (TSP, Floyd-Warshall) ⇒ dense ⇒ matrix.
• Mutating a defaultdict while querying it: NETWORK["NONEXISTENT_ZONE"] on a defaultdict creates the empty key as a side effect. That is why we convert to dict once construction is done.
• Tip: get into the habit of validating cheap invariants after building the graph (sum of degrees = 2m, positive weights if the algorithm demands them). Five lines of assert save hours of debugging.

1. Degrees of the canonical network. Write a function degrees(graph) that, from the adjacency list NETWORK, returns a dict {node: degree}. Use it to verify that the sum of degrees is 2m and to find Rutalia's best-connected zone and its most fragile one.
2. Converting between representations. Write list_to_matrix(graph, nodes) converting the adjacency list into a matrix (with math.inf for missing edges and 0 on the diagonal) and matrix_to_list(matrix, nodes) for the reverse conversion. Check that a round trip returns the original graph.
3. Directed version. Rutalia learns that the RIO→CEN segment becomes one-way (only from RIO towards CEN) due to roadworks. Build the network as a directed graph (each two-way street is two directed edges, and RIO–CEN just one) and write a function returning the in-degree and out-degree of each zone. Which zone loses accessibility?

Exercise 1:

Since each neighbor in the adjacency list corresponds to exactly one incident edge, len(neighbors) is directly the degree. max(g, key=g.get) returns the key with the maximum value.

Exercise 2:

Note: since the adjacency list already stores each undirected edge in both directions, there is nothing to symmetrize: the matrix comes out symmetric on its own.

Exercise 3:

RIO loses inbound accessibility: before, it could be reached from ALM, CEN and PAR (degree 3); now it can no longer be reached from CEN (in-degree 2), even though you can still leave RIO towards all three. In directed graphs, in and out tell different stories.

The debt is settled: Rutalia's routes are now first-class mathematics. A graph is a pair (V, E), with directed and weighted variants; it is represented with an adjacency matrix (O(n²) memory, O(1) lookup, ideal for dense graphs like the TSP matrix) or with an adjacency list (O(n+m), neighbor iteration proportional to the degree, the default choice in sparse networks like a street map). And sometimes it isn't even stored: the grid from 01-03 was an implicit graph. On the table sits the canonical graph of Rutalia: 9 zones, 15 segments in minutes, with a trap avenue (ALM–CEN, 12 min) that already hints at the next lesson's question. Because having the network in memory is useless if we don't know how to traverse it: in 03-02 we will learn BFS and DFS, the two fundamental exploration orders, and with them we will answer real operational questions: which zones remain reachable if a street is closed? How many segments away is the farthest delivery point?