Graphs: Maps, Mazes, and Exploring Without Getting Lost

Last week closed on a warning: everything the notebook touched shrank cleanly — peel a letter, cut a branch, and it never came back. Tonight we walk into the country where that stops being true. The subway map, your social network, your degree's prerequisite chart, the internet itself — they are all graphs: dots connected by links, where the links can loop back around. You can walk in circles. So before graphs give us anything, we have to learn the explorer's first skill: how to visit everything, once, without getting lost.

Session planHow we will spend the two sessions

Section 1The world stops shrinking politely

You already live on graphs. The subway map: stations connected by track. Your social network: people connected by friendships. Your degree: courses connected by "take this first" arrows. The internet: pages connected by hyperlinks, routers connected by cables. In every one of them, the object is the same two-ingredient thing:

So what's new? Trees from last week were graphs too — dots and links, with one promise attached: no loops. Cut a branch and it fell away forever; every step down the org chart made the problem smaller. Graphs make no such promise. Subway lines form circles on purpose. Your friend's friend's friend can be you. And that one missing promise changes everything about how you explore:

Here is the good news hiding in that picture: the discipline turns out to be small. Two exploration strategies — one patient, one bold — plus a pocketful of breadcrumbs, and every graph on Earth opens up. Everything else this week (ordering tasks, finding islands) falls out of those two strategies almost for free.

Section 2How a computer holds a map

Before exploring a graph, a program has to hold one, and there are exactly two classic ways. Both answer the same question — "who is linked to whom?" — with opposite trade-offs. Take six people, A through F, with seven friendships:

In Python, the friends list is a dictionary of lists, and that's the entire data structure this week runs on:

friends = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C", "F"],
    "E": ["C", "F"],
    "F": ["D", "E"],
}

Which costume should you reach for? One honest sentence each. The friends list is lean: it stores only the links that exist, and real-world graphs are overwhelmingly sparse — two million users with 200 friends each is 400 million list entries, while the checkbox table for the same network is four trillion boxes, almost all of them recording the non-news that two strangers aren't friends. The table's one superpower is the instant lookup: "are A and D linked?" is one peek at one box, where the friends list has to skim A's whole list. Sparse graph, walking along links (which is everything we do tonight): friends list. Small dense graph, hammering "are these two linked?" questions: table. That's the whole buying guide.

Section 3The ripple: breadth-first search

Now, exploring. Strategy one is the patient one. Drop a stone in a pond where you're standing. The ripple reaches everything 1 link away first. Then everything 2 links away. Then 3. It never skips ahead — water doesn't tunnel. Computer scientists call this breadth-first search, BFS; we'll call it the ripple.

To run a ripple on a computer you need two pieces of bookkeeping, and both are household objects:

• The line at the door. When you visit a dot, its not-yet-seen neighbors get in line. You always serve the front of the line — first come, first served — so everyone from ring 1 gets served before anyone from ring 2, automatically. (The data structure is a queue, and you met it in Week 6: this is what queues are for.)
• Breadcrumbs. The moment a dot gets in line, drop a breadcrumb on it: "seen." A dot with a breadcrumb never gets in line again. This is the discipline from §1 — it is exactly what stops the loop in the gold pentagon from trapping you. No breadcrumbs, infinite circles; breadcrumbs, every dot visited exactly once. (It's the humblest notebook we've ever kept: it doesn't even store answers, just "been here.")

from collections import deque

def ripple(friends, start):
    """Visit everything reachable from start, nearest rings first."""
    line = deque([start])              # the line at the door
    crumbs = {start}                   # breadcrumbs: already seen
    while line:
        person = line.popleft()        # serve the front — first come, first served
        print(person)
        for buddy in friends[person]:
            if buddy not in crumbs:  # no breadcrumb yet?
                crumbs.add(buddy)
                line.append(buddy)     # back of the line

Ten lines, and two of them are the whole story: popleft (patience — serve the nearest first) and crumbs (discipline — never twice). Want the actual shortest route, not just its length? When a buddy gets in line, jot down who put them there; walking those jottings backward from the destination spells out the route. You've seen that move twice already — it's the walk-back from the DP weeks, wearing hiking boots.

Section 4The maze-walker: depth-first search

Strategy two is the bold one. Forget rings — plunge. At every junction, take the first unexplored hallway and keep going deeper until you hit a dead end (no unvisited neighbors). Then back up — only as far as the last junction that still has an untried hallway — and plunge again. It's exactly how you solve a hedge maze with one hand on the wall. The official name is depth-first search, DFS; we'll call it the maze-walker.

Its bookkeeping is the mirror image of the ripple's. Instead of a line at the door, the maze-walker keeps the trail of forks behind it — the junctions it passed on the way in, newest on top, so "back up" means "return to the most recent fork." That last-in-first-out object is a stack (Week 6 again). And here's the lovely part: recursion keeps that trail for you, for free. Every recursive call is a fork remembered; every return is backing up one fork. You watched the call stack do precisely this in Notes 01's recursion demo:

def maze_walk(friends, person, crumbs=None):
    """Go deep. When stuck, back up to the last fork and try the next hallway."""
    if crumbs is None:
        crumbs = set()
    crumbs.add(person)
    print(person)
    for buddy in friends[person]:
        if buddy not in crumbs:
            maze_walk(friends, buddy, crumbs)   # the call stack IS the trail of forks

Same breadcrumbs, same "visit everything once" guarantee — different order, and the order is the whole personality. When does each win?

Now race them. Thirteen dots, plenty of loops, and — notice — a little triangle in the corner that no link reaches. Tap a mode, then tap any dot:

Some things to try:

1. Ripple from A and read the colors: B and E light up as ring 1, then C and F, then D, G, I, then H and J — the visit numbers never jump ahead of the rings. That picture is the shortest-path argument.
2. Maze-walk from A and watch it bolt: A, B, C, D, H, J — six dots deep before it ever looks back, the trail of forks stacking up behind it. Same thirteen dots by the end (an island is an island either way), order entirely different.
3. Switch to Shortest route, tap E, then H. Four links, lit in green. Try to beat it by eye. Then tap A, then K — and meet §6 early.
4. Ripple from K. Three dots and done: the mainland might as well not exist. Keep that feeling — it's the whole of §6.

Section 5Getting dressed in the right order

New kind of graph, new superpower. So far our links had no direction — a friendship points both ways. But "socks before shoes" points one way. A graph whose links are arrows is a directed graph, and the everyday version is any to-do list with dependencies: course prerequisites, build systems, recipes, and the oldest scheduling problem in the world — getting dressed.

How do you find such an order? The method you already use every morning, stated out loud:

And the sting in the tail is the best part. When can this get stuck — tasks remaining, but none of them doable? Only when every remaining task waits on another remaining task, round and round: a loop in the arrows. "A requires B, B requires C, C requires A" — a degree where two courses are each other's prerequisite. No valid order exists, not because we searched badly, but because the demand is self-contradictory. So the dressing method is secretly two tools in one: it produces an order when one exists, and its failure is a proof that a cycle exists. When npm, or make, or your university's registrar prints circular dependency detected — this is the tool that said it, getting stuck on purpose.

Try the morning routine yourself — then curse it:

Two honest notes the demo makes vivid. First, many valid orders usually exist — the wardrobe game will tell you exactly how many its rules allow, and any of them is a full-credit answer; "the" topological order is almost never unique. Second, when the cursed arrow is in place, notice where you get stuck: not immediately, but after the free items run out — which is exactly how real circular-dependency bugs feel. Everything builds fine until suddenly nothing does.

def get_dressed(tasks, needs):      # needs[t] = set of t's prerequisites
    done = []
    while len(done) < len(tasks):
        ready = [t for t in tasks
                 if t not in done and needs[t] <= set(done)]
        if not ready:
            return None              # stuck with tasks left = there's a loop
        done.append(ready[0])         # anything ready is fine — hence many valid orders
    return done

Section 6Islands: who can reach whom

One more gift, and it's almost free. In Demonstration 1, rippling from A touched ten dots and rippling from K touched three — and no run ever touched all thirteen. The map isn't one territory; it's two islands. Dots A–J can all reach each other; K, L, M can all reach each other; and no link bridges the gap. Each island is called a connected component, and finding them all takes exactly one idea:

def count_islands(friends):
    crumbs, islands = set(), 0
    for person in friends:
        if person not in crumbs:
            islands += 1                       # an unseen dot = a new island
            ripple_into(friends, person, crumbs)   # §3's ripple, sharing the crumb set
    return islands

Why care? Because "are these two things connected at all?" is a question the real world asks constantly. Friend circles that never overlap. A power-grid failure that splits a region into cells — which neighborhoods lost contact with the plant is a components question. "Is this maze even solvable" is "do start and exit share an island." Network engineers monitoring whether an outage has partitioned the internet are counting components on a very large, very expensive graph. The algorithm is the one above, every time.

One honest sentence about one-way streets: when the links are arrows, "I can reach you" stops implying "you can reach me" (every follower of a celebrity knows this), so "island" needs more care to define there — a story for a later course; this week's two-way islands are the workhorse case.

Section 7Before next session