Graphs and How to Store Them

That network was a graph: nodes connected by edges, where connections can loop back.

Friendships loop, and the dict in lesson 5-3 contained a concrete example, since you leads to ana, ana to cai, cai to ben, and ben back to you. A tree can never do that, because nothing below a node may point back up to it.

So it was a graph all along, and the seen set that felt like defensive coding was actually the one thing making the traversal terminate.

That dict-of-lists format has an official name, introduced in this lesson: the adjacency list.

The most general structure

A graph is a set of nodes, also called vertices, plus a set of edges, which are the pairwise connections between them. That is the entire definition, and it fits an enormous range of data.

• Cities and flights, intersections and roads.
• People and friendships, web pages and links.
• Courses and prerequisites, tasks and must-happen-before relationships.

Two choices define a graph's flavor. Edges can be undirected, like a friendship that goes both ways, or directed, like a prerequisite that points one way only. Edges can also carry weights such as flight cost or road minutes, or carry none at all.

Those two choices are not cosmetic. A road network with one-way streets and a road network without them need different algorithms, and lesson 9-3 shows what breaks when weights enter the picture.

A tree turns out to be a special graph: connected, free of cycles, with one designated root. Dropping those restrictions gives the general case, and it is why the BFS from lesson 5-3 needed its seen set, since in a graph a path can circle back to where it started.

Two ways to store one

An adjacency list is a dict mapping each node to a list of its neighbors. Memory is O(nodes + edges), and asking who neighbors X is a single O(1) dict lookup.

This is the default choice, because real graphs are usually sparse, meaning each node touches only a few of the others. A social network user follows hundreds of accounts, not hundreds of millions.

An adjacency matrix is an n × n grid of 0s and 1s, where matrix[i][j] = 1 means an edge runs from node i to node j. Asking whether X and Y are directly connected is O(1) indexing, which is its one clear advantage.

The cost is that memory is O(n²) no matter how few edges exist, since the grid reserves a cell for every possible pair. A million-node graph needs 10¹² cells, and almost all of them hold zero.

The table is the whole trade in three rows. A matrix answers one question faster and pays for it on both memory and neighbor listing, which is why the traversals in the next two lessons are all written against adjacency lists.

Building an adjacency list

Turning a plain edge list into an adjacency list is a five-line idiom worth memorizing.

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]

adj = {}
for u, v in edges:
    adj.setdefault(u, []).append(v)
    adj.setdefault(v, []).append(u)

for node in sorted(adj):
    print(node, adj[node])

Output

A ['B', 'C']
B ['A', 'D']
C ['A', 'D']
D ['B', 'C', 'E']
E ['D']

setdefault creates the empty neighbor list the first time a node appears, which removes any need to collect the nodes in a separate pass before the edges.

Each undirected edge is recorded in both directions, and that is the line people forget. Storing only adj[u].append(v) would make the graph directed, so a BFS starting at E would find nothing.

The output shows the doubling clearly. Five input edges produced ten entries across the lists, since every edge appears once from each endpoint.

D came out with three neighbors because it appears in three of the five edges, and reading the lists back gives an easy sanity check on any hand-built graph.

Degree in an airport network

build_adj is the idiom from the demo, and busiest reports the node with the most neighbors.

edges = [("sfo", "lax"), ("sfo", "sea"), ("lax", "jfk"), ("sea", "jfk"), ("jfk", "bos")]

def build_adj(edges):
    adj = {}
    for a, b in edges:
        adj.setdefault(a, []).append(b)
        adj.setdefault(b, []).append(a)
    return adj

def busiest(adj):
    best = None
    for node in adj:
        if best is None or len(adj[node]) > len(adj[best]):
            best = node
    return best

adj = build_adj(edges)
for node in sorted(adj):
    print(node, "degree", len(adj[node]))
print("busiest:", busiest(adj))

Output

bos degree 1
jfk degree 3
lax degree 2
sea degree 2
sfo degree 2
busiest: jfk

A node's neighbor count is called its degree, and with an adjacency list it is len(adj[node]), one O(1) lookup plus a length read. A matrix would have to scan an entire row of n cells to answer the same question.

busiest tracks the best node seen so far, with best is None covering the first iteration so the loop needs no separate setup. The one-liner version is max(adj, key=lambda n: len(adj[n])), the same max idiom as the vote counter in lesson 6-3.

jfk wins with degree 3 because it touches lax, sea, and bos. Three of the other airports tie at 2, and this loop returns whichever it meets first, so a tie-breaking rule would have to be added if it mattered.

Summing all the degrees gives 10 for 5 edges, which is not a coincidence. Every edge contributes 1 to each endpoint, so the degrees of an undirected graph always total twice the edge count.

An adjacency matrix is a disaster there because it would need 10¹⁸ cells while only about 5 × 10¹¹ real edges exist.

The arithmetic is unforgiving. n² = (10⁹)² = 10¹⁸ cells to record roughly 500 × 10⁹ actual follows, which makes about 99.99995% of the grid zeros.

Memory is O(n²) regardless of sparsity, so the matrix cannot take advantage of the fact that each user follows only 500 accounts. No amount of emptiness shrinks it, because the size is decided by the node count alone.

The adjacency list stores only the edges that exist, O(n + e), which for these numbers is around 5 × 10¹¹ entries rather than 10¹⁸ cells, a factor of about two million less.

Matrices shine only on small, dense graphs where most pairs really are connected, and there the O(1) edge test is worth the grid.