Quiz
Warm-up from lesson 5-3: the friend network you ran BFS over was stored as a dict mapping each person to a list of their friends. What kind of structure was that network, really?
The most general structure
A graph is a set of nodes (also called vertices) plus a set of edges, the pairwise connections between them. That's it, and it is everywhere:
- cities + flights, intersections + roads
- people + friendships, web pages + links
- courses + prerequisites, tasks + "must happen before"
Two choices define a graph's flavor. Edges can be undirected (friendship goes both ways) or directed (a prerequisite points one way). Edges can also carry weights (flight cost, road minutes), or not.
A tree, it turns out, is just a special graph: connected, no cycles, one root. Drop those restrictions and you have the general case. That is why your BFS from lesson 5-3 needed the seen set: in a graph, unlike a tree, paths can circle back.
Two ways to store one
Adjacency list: a dict mapping each node → list of its neighbors. Memory is O(nodes + edges), and asking "who neighbors X?" is one O(1) dict lookup. This is the default choice, because real graphs are usually sparse (each node touches few others).
Adjacency matrix: an n × n grid of 0s and 1s where matrix[i][j] = 1 means an edge from node i to node j. Asking "are X and Y directly connected?" is O(1) indexing, but memory is O(n²) no matter how few edges exist. A million-node graph needs 10¹² cells, almost all zero.
| question | adjacency list | matrix |
|---|---|---|
| list X's neighbors | O(1) to find the list | O(n) scan the row |
| is X→Y an edge? | O(neighbors of X) | O(1) |
| memory | O(n + e) | O(n²) |
Code exercise · python
Run this. Building an adjacency list from a plain edge list is a five-line idiom worth memorizing. `setdefault` creates the empty neighbor list the first time a node appears. Each undirected edge is recorded in BOTH directions.
Code exercise · python
Your turn: an airport network. `build_adj` is the idiom from the demo (record each undirected edge in BOTH directions). Then implement `busiest`: the node with the most neighbors. A node's neighbor count is called its **degree**, and with an adjacency list it is just `len(adj[node])` — one O(1) lookup plus a length read.
Quiz
A social network has 1 billion users, each following about 500 accounts. Why is an adjacency matrix a disaster here?