Chapter 7 — Graphs and the Shape of Connection

“There is no problem in all mathematics that cannot be solved by direct counting. But it is not always… the most appropriate.” — Ernst Mach, on choosing the right representation; and famously, the field of graph theory itself was born when Leonhard Euler refused to count the Königsberg bridge-walks one by one and instead drew the connections.

“For as in one body we have many members, and the members do not all have the same function, so we, though many, are one body in Christ, and individually members one of another.” — Romans 12:4–5

Why This Matters

Last week you built a tree: a structure with a root, parents, and children, where every node had exactly one path back to the top. A tree is a graph with a rule attached — no cycles, one parent each. This week we take that rule away, and the structure that remains is the most general, most powerful, and most common shape in all of computing.

A graph is just things and the connections between them. That’s it. Vertices and edges. And once you learn to see it, you will see it everywhere — because the world is mostly connections, and most of the interesting questions a program gets asked are questions about connections.

Here is the move that separates an architect from a coder, and it is the whole first half of this chapter: the hardest part of graph problems is not the algorithm. It is recognizing that you have a graph at all. A junior engineer reads “find the shortest sequence of approvals to get this expense signed off” and starts writing nested loops and special cases. An architect reads the same sentence, hears the word sequence and the word connection, and says: that’s a graph, and the answer is breadth-first search. The algorithm is the easy part — it fits on a napkin. The architecture is in the seeing.

You have, in fact, been using graphs since Coding 1 without naming them. A class diagram is a graph (classes connected by “uses” and “extends”). A call stack is a path through the graph of “who calls whom.” The import lines at the top of every file you have ever written describe a dependency graph, and the reason a circular import is an error is that the graph has a cycle the loader can’t resolve. The internet is a graph. A friend list is a graph. The cross-references in a study Bible are a graph. The roads between cities, the prerequisites between courses, the references between web pages that Google ranks — graphs, all of them.

And here is where the cost-thesis of Phase 1 comes back with teeth. Once you see the graph, you have a choice: how do you store it? There are two classic answers, and they sit at opposite ends of the speed-versus-memory tradeoff you have been measuring all term. One is lean on memory and slow at a particular question; the other is fast at that question and fat on memory. Neither is “correct.” The right one depends on how dense your graph is and which queries you run most. That choice — made before you write the traversal — is the architect’s decision this week.

The Christian question for the week is the one the body of Christ has always lived: how are we bound to one another? Paul reaches for a graph to answer it. Not a list of believers, not a hierarchy with one person on top — a body, in which “the members… are individually members one of another.” Many vertices, many edges, one connected whole, where the suffering of one part is felt by all because the parts are connected. The communion of saints is a graph, and a richly connected one. Hold that picture; we will come back to it when we ask what it means for a graph to be “connected,” and what it means when part of it becomes an island.

This week you learn to see the graph, to name its parts, to store it two ways and pay for each, and to walk it with the two great traversals every working engineer knows cold. Let’s begin.

7.1 — Seeing the Graph: The First Architectural Skill

Before any vocabulary, before any code, train the eye. A problem is a graph problem when it has entities and relationships between them, and the question you’re being asked is about the relationships.

Here are problems that do not look alike on the surface but are the same graph problem underneath:

Read that table twice. Every row is a different domain — logistics, social, finance, build systems, ministry — and every row is one of four or five graph questions you will learn to answer this week: shortest path, reachability, connectivity, ordering, cycles. The domains are infinite. The questions are few.

Coach’s Note — The tell that you are looking at a graph is the word between, or through, or connected, or depends on, or reachable, or path. When a spec uses one of those words, stop and ask: what are my vertices, and what are my edges? If you can answer those two questions, you have modeled the problem, and modeling is ninety percent of the work. The traversal that answers the question is the napkin part.

The discipline is to write down, in one sentence each, what is a vertex and what is an edge, before you write a line of code. Get those two sentences right and the rest follows. Get them wrong — model the wrong thing as a vertex — and no clever algorithm will save you.

7.2 — The Vocabulary (Vertex, Edge, and the Words That Modify Them)

A graph G = (V, E) is a set of vertices (also called nodes) and a set of edges connecting pairs of them. That is the whole definition. Everything else is an adjective on top of it, and each adjective is a modeling decision with consequences. Learn these cold; you will use them for the rest of your career.

• Vertex / node. A thing. A person, a city, a course, a module. The dots.
• Edge. A connection between two vertices. The lines.
• Directed vs. undirected. In an undirected graph, an edge between A and B goes both ways — if Maya is Marcus’s small-group partner, Marcus is Maya’s. Friendship, “shares a road with,” “is in the same fellowship as.” In a directed graph (or digraph), edges have a direction — A → B does not imply B → A. “Maya follows Marcus” on social media, “course X is a prerequisite for course Y,” “module A imports module B.” The arrow matters. Choosing directed vs. undirected is the most common modeling mistake juniors make: model “follows” as undirected and your answer is wrong before you start.
• Weighted vs. unweighted. An unweighted edge just says “connected.” A weighted edge carries a number — a distance, a cost, a travel time, a strength. “Maya and Marcus are connected” is unweighted; “the road from Capernaum to Jerusalem is 120 miles” is weighted. The weight changes the question: in an unweighted graph “shortest path” means fewest edges; in a weighted graph it means least total weight, which can be a different path entirely.
• Degree. The number of edges touching a vertex. In Romans-12 terms, a highly-connected member — many edges — has high degree. In a directed graph you split it into in-degree (arrows coming in) and out-degree (arrows going out).
• Path. A sequence of vertices where each consecutive pair is connected by an edge. Maya → Priya → Esther is a path. The length of a path is the number of edges in it (here, 2).
• Cycle. A path that starts and ends at the same vertex without repeating an edge. Maya → Marcus → Priya → Maya is a cycle. A graph with no cycles is acyclic. (A tree, from last week, is a connected acyclic graph. Now you know exactly what a tree is in graph terms.)
• Connected. An undirected graph is connected if there is a path between every pair of vertices — no islands. If it has islands, each island is a connected component. This word is the whole back half of the chapter, and the whole apologetic frame: is the body one, or has it fractured into pieces that can no longer reach one another?

Coach’s Note — The four adjective-pairs — directed/undirected, weighted/unweighted — are a two-by-two grid, and which cell your problem lives in is a modeling decision you make before coding. A road map: undirected, weighted. Twitter follows: directed, unweighted. Flight prices: directed (one-way fares differ), weighted. Get the cell wrong and you’ll solve the wrong problem flawlessly. Name the cell first.

7.3 — Two Ways to Store a Graph (and the Tradeoff Between Them)

Now the architect’s choice. You have seen the graph and named its parts. How do you put it in memory? Two classic representations, sitting at opposite ends of the speed-versus-memory tradeoff you have measured all term.

The adjacency list

Keep, for each vertex, the collection of its neighbors. In Python, a dict mapping each vertex to a set (or list) of the vertices it connects to.

# An adjacency LIST: vertex -> set of neighbors. Undirected, so each
# edge is recorded in BOTH directions.
graph = {
    "Maya":   {"Marcus", "Priya"},
    "Marcus": {"Maya", "Priya", "Daniel"},
    "Priya":  {"Maya", "Marcus", "Esther"},
    "Daniel": {"Marcus", "Esther"},
    "Esther": {"Priya", "Daniel"},
}

# "Who are Maya's neighbors?" — O(1) to find the set, O(degree) to walk it.
print(graph["Maya"])              # {'Marcus', 'Priya'}

# "Is there an edge Maya--Daniel?" — O(degree(Maya)) to check membership.
print("Daniel" in graph["Maya"])  # False

The adjacency list stores exactly the edges that exist and nothing else. Its space is O(V + E) — one entry per vertex, plus two stored endpoints per undirected edge. For a sparse graph — few edges relative to the number of possible edges — this is wonderfully lean. It is also the natural representation for the question “who are my neighbors?”, which is the question most traversals ask on every step.

The adjacency matrix

Number the vertices 0, 1, 2, …, V−1, and keep a V×V grid where cell [i][j] is 1 if there is an edge between vertex i and vertex j, and 0 otherwise.

# An adjacency MATRIX for the same 5 people.
# Order: Maya=0, Marcus=1, Priya=2, Daniel=3, Esther=4
labels = ["Maya", "Marcus", "Priya", "Daniel", "Esther"]
matrix = [
    [0, 1, 1, 0, 0],   # Maya   -- Marcus, Priya
    [1, 0, 1, 1, 0],   # Marcus -- Maya, Priya, Daniel
    [1, 1, 0, 0, 1],   # Priya  -- Maya, Marcus, Esther
    [0, 1, 0, 0, 1],   # Daniel -- Marcus, Esther
    [0, 0, 1, 1, 0],   # Esther -- Priya, Daniel
]

# "Is there an edge Maya--Daniel?" — O(1). Two index operations. THIS is the win.
print(matrix[0][3])   # 0  (no edge)
print(matrix[0][1])   # 1  (Maya--Marcus, yes)

For an undirected graph the matrix is symmetric (cell [i][j] equals cell [j][i]), and the diagonal is usually 0 (no self-loops). Edge lookup — “is there an edge between A and B?” — is O(1): two array indexes, the array’s superpower from Chapter 2. But the price is brutal on space: the matrix is O(V²) no matter how few edges you have. A graph of 10,000 vertices needs a hundred-million-cell grid even if there are only a dozen edges in it.

The tradeoff, in one table

The rule of thumb, burn it in: sparse graph → adjacency list; dense graph → adjacency matrix. Most real-world graphs are sparse — your friends are not friends with everyone, cities are not connected to every other city, a module imports a handful of others, not all of them — so the adjacency list is the right default the overwhelming majority of the time. Reach for the matrix when the graph is genuinely dense, when it is small enough that V² doesn’t hurt, or when the one query you run constantly is “is there an edge between these two?” and you need it in O(1).

The runnable code/graph_representations.py builds the same graph both ways and measures the actual bytes on a sparse 200-vertex chain and a dense 200-vertex complete graph. The numbers tell the story without any rhetoric:

SPARSE graph (a 200-vertex chain, E = V - 1):
  V=200  E=199   density=1%
  adjacency list   ~   63,002 bytes      <- list wins big
  adjacency matrix ~  348,664 bytes

DENSE graph (200 vertices, every pair connected):
  V=200  E=19,900  density=100%
  adjacency list   ~ 1,701,402 bytes
  adjacency matrix ~   348,664 bytes     <- matrix wins big

Look at the matrix’s number: it is identical for the sparse and the dense graph — 348,664 bytes both times — because the matrix pays V² regardless of how many edges exist. The list’s number swings by 27× between sparse and dense, because the list pays for exactly the edges present. That flat-cost-versus-pay-for-what-you-use shape is the tradeoff. There is no universally right answer; there is only the right answer for your density and your queries.

Coach’s Note — This is the Chapter 2 lesson wearing new clothes. The matrix buys O(1) edge lookup with O(V²) memory — speed for space, the oldest trade in the book. The architect doesn’t ask “which representation is better?” There is no better. The architect asks “how dense is this graph, and which query do I run a million times?” Answer those two, and the representation chooses itself. That is the whole job, at the smallest scale.

7.4 — Breadth-First Search: The Queue Gives You Shortest Hops

You have the graph stored. Now you walk it. There are two canonical ways, and the first is breadth-first search — BFS.

BFS explores in rings. Start at a vertex; visit all its neighbors (distance 1); then all of their unvisited neighbors (distance 2); then theirs (distance 3); and so on, expanding outward in waves of increasing distance. Because it always finishes the closer ring before touching the farther one, the first time BFS reaches a vertex, it has reached it by a shortest path — fewest edges. That is BFS’s signature gift: shortest number of hops in an unweighted graph.

And the engine that makes the rings happen is a structure you built two weeks ago: the queue. Remember Chapter 4 — first in, first out. BFS puts each newly-discovered vertex on the back of the queue and always processes the one at the front. Because the front always holds the oldest discovery, you always expand the closest unexplored vertex next. The queue is the ring discipline. This is exactly the callback the queue was built for.

from collections import deque

def bfs_shortest_hops(adj, start, goal):
    """Fewest hops from start to goal, or None if unreachable."""
    if start == goal:
        return 0
    visited = {start}
    queue = deque([(start, 0)])           # (vertex, distance from start)
    while queue:
        vertex, dist = queue.popleft()    # FIFO: oldest out first -> closest first
        for neighbor in adj.get(vertex, ()):
            if neighbor == goal:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)     # mark on ENQUEUE, not on dequeue
                queue.append((neighbor, dist + 1))
    return None

Two details that are not optional, and that the Common Bugs section will flog you for getting wrong:

1. Use collections.deque, not a list, as the queue. A deque.popleft() is O(1); a list.pop(0) is O(n) because it shifts every element left (the exact quadratic trap from Chapter 2’s Common Bugs). A BFS on a list-as-queue is secretly O(V²) for no reason.
2. Mark a vertex visited the moment you enqueue it, not when you dequeue it. If you wait until dequeue, the same vertex can be enqueued many times before it’s ever processed, and your “shortest” answer and your performance both fall apart.

Run code/traversal.py on the ministry dataset and BFS answers real questions:

Maya -> Hannah: 3 hops   path: Maya -> Priya -> Esther -> Hannah
Maya -> Tobias: 6 hops   path: Maya -> Priya -> Esther -> Hannah -> Ruth -> Samuel -> Tobias
Maya -> Silas:  unreachable (no path)

“Three introductions to reach Hannah.” “Six to reach Tobias.” “You cannot reach Silas at all.” That last line is connectivity poking through, and we’ll name it in §7.6. To recover the actual path and not just its length, carry a parent map — record, for each vertex, who you reached it from — then walk the parents backward from the goal. That’s bfs_path in the file.

Coach’s Note — “BFS for shortest path” has one giant asterisk: it gives shortest number of edges, which is the true shortest path only when every edge costs the same — an unweighted graph. The moment edges carry different weights (miles, dollars, minutes), BFS’s ring logic breaks, because three short hops can total more than one long one. For weighted shortest paths you need Dijkstra (§7.7). Knowing which tool the weighting demands is, once again, the architect’s whole edge.

7.5 — Depth-First Search: The Stack Goes Deep

The other canonical walk is depth-first search — DFS. Where BFS fans out in rings, DFS plunges: from the start, follow one edge as far as it goes, then backtrack one step and try the next unexplored edge, and so on, going as deep as possible before retreating. It is the natural tool for reachability (“can I get from A to B at all?”), connected components (“what’s the whole island A lives on?”), and cycle detection (“does following the edges ever loop back?”).

DFS’s engine is the other structure from Chapter 4: the stack — last in, first out. You can write DFS with an explicit stack, or — more commonly and more cleanly — let recursion do it for you, because the call stack is a stack. Recursion was last week’s whole topic (Chapter 6, trees); DFS is recursion let loose on a structure that, unlike a tree, can loop back on itself. That one difference — graphs have cycles, trees don’t — is why DFS must track which vertices it has already visited, or it will recurse forever around a cycle.

def dfs_reachable(adj, start):
    """Every vertex reachable from start (recursive DFS).

    Recursion uses the call STACK. The `visited` set is NOT optional:
    a graph can have cycles, and without it DFS recurses forever.
    """
    visited = set()

    def visit(vertex):
        visited.add(vertex)
        for neighbor in adj.get(vertex, ()):
            if neighbor not in visited:     # the line that stops infinite loops
                visit(neighbor)

    visit(start)
    return visited

def are_connected(adj, a, b):
    return b in dfs_reachable(adj, a)

The iterative form makes the stack explicit, and you reach for it when a graph is deep enough to blow Python’s default recursion limit (about 1000 frames):

def dfs_reachable_iterative(adj, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()                # LIFO: newest out first -> go deep
        if vertex in visited:
            continue
        visited.add(vertex)
        for neighbor in adj.get(vertex, ()):
            if neighbor not in visited:
                stack.append(neighbor)
    return visited

Stare at the difference between this and the BFS loop. The only real change is the data structure: BFS uses deque.popleft() (take the oldest, FIFO) and DFS uses stack.pop() (take the newest, LIFO). Swap the queue for a stack and breadth-first becomes depth-first. Same skeleton, opposite shape of exploration, opposite set of questions answered. That is one of the most elegant facts in all of data structures, and it is a direct payoff of having built both a stack and a queue by hand in Chapter 4.

On the ministry data, DFS answers the connectivity questions:

reachable from Maya: 12 people
Maya connected to Hannah? True
Maya connected to Silas?  False

Maya can reach twelve of the fourteen people. The two she can’t — Phoebe and Silas — form their own little island, connected to each other but to no one else. DFS found the island by failing to reach it, which is exactly how you detect one.

Coach’s Note — “BFS or DFS?” is decided by the question, not by taste. Shortest path / fewest hops → BFS, every time, because only the ring discipline guarantees shortest-first. Just reachability, or the whole component, or is-there-a-cycle → DFS, because it’s simpler and recursion makes it nearly free to write. If you only need “is there ANY path,” DFS is the lighter tool. If you need “the shortest path,” it must be BFS. Picking the wrong one isn’t a crash — it’s a subtly wrong or needlessly slow answer, the most expensive kind of bug.

7.6 — Connected Components: Counting the Islands

Now the apologetic question made literal. An undirected graph is connected if you can get from any vertex to any other. If you can’t, it splits into connected components — maximal islands, each fully reachable within itself but cut off from the others.

You already have the tool. Run DFS (or BFS) from a vertex; everything it reaches is one component. Pick any vertex you haven’t reached yet and run again; that’s the next component. Repeat until every vertex belongs to some component. Count the runs, and you’ve counted the islands.

def connected_components(adj):
    """Return a list of sets, one per connected component."""
    seen = set()
    components = []
    for start in adj:                       # try every vertex as a possible new island
        if start not in seen:
            component = dfs_reachable(adj, start)   # the whole island start lives on
            seen |= component
            components.append(component)
    return components

On the ministry data this returns two components: the twelve-person main fellowship around Maya, and the two-person {Phoebe, Silas}. Two islands. The body is not, in this dataset, fully one — there is a pair that no chain of relationships connects to the rest. An architect reading that doesn’t just see a number; they see a finding: “these two members are isolated from the fellowship; if the goal is one connected body, here is exactly where to build a bridge.” The graph turned a vague worry — is anyone falling through the cracks? — into a precise, actionable answer.

Coach’s Note — Connected components is the algorithm behind a hundred real features: “people you may know” (everyone in your component you don’t already know), “clusters in this dataset,” “which servers can still talk to each other after the network split,” “which files form an independent module.” Once you can count islands, you can answer all of them. One small algorithm, vast reach — the recurring shape of this whole chapter.

7.7 — A Note on Weighted Shortest Paths: Dijkstra’s Idea

BFS gives the shortest path when every edge costs the same. But the road from Capernaum to Jerusalem isn’t the same length as the road to the next village, and the cheapest flight isn’t always the one with the fewest legs. When edges carry weights, “shortest” means least total weight, and BFS’s ring logic — which counts edges, not weights — no longer works. Three cheap hops can beat one expensive one, and BFS would wrongly prefer the single hop.

The classic fix is Dijkstra’s algorithm, and you do not need to memorize its implementation this week — but you should understand its idea, because the idea is the architect’s lesson and the Hard tier of this week’s project invites you to attempt it.

The idea is greedy expansion by cheapest-known-distance. Keep a running best-known distance to every vertex (start at 0 for the source, infinity for everyone else). Repeatedly pick the unfinished vertex with the smallest known distance, finalize it, and update its neighbors: “I can reach you through me for my_distance + edge_weight — is that better than your current best?” Because you always finalize the closest unfinished vertex first, by the time you finalize a vertex its distance is truly minimal. It is BFS’s “closest first” instinct, but measured in total weight instead of hop count.

The tool that makes “pick the smallest known distance” fast is a priority queue — a queue that hands you the minimum element, not the oldest. Python gives you one in the standard library: heapq, a binary heap (a cousin of last week’s trees — a tree-shaped array that keeps the smallest element at the root in O(log n) per operation).

import heapq

def dijkstra(weighted_adj, start):
    """Least-total-weight distance from start to every vertex.
    weighted_adj: vertex -> list of (neighbor, weight).
    """
    dist = {start: 0}
    pq = [(0, start)]                       # a min-heap of (distance, vertex)
    while pq:
        d, vertex = heapq.heappop(pq)       # the cheapest-known unfinished vertex
        if d > dist.get(vertex, float("inf")):
            continue                        # a stale, already-improved entry; skip
        for neighbor, weight in weighted_adj.get(vertex, ()):
            new_dist = d + weight
            if new_dist < dist.get(neighbor, float("inf")):
                dist[neighbor] = new_dist   # found a cheaper route to neighbor
                heapq.heappush(pq, (new_dist, neighbor))
    return dist

That’s the whole greedy loop. It runs in O((V + E) log V) with a heap — fast enough for very large graphs — and it is the engine inside every routing app, every shortest-route feature, every “cheapest path” you have ever used. (One honest caveat: Dijkstra assumes non-negative weights. Negative-weight edges break the greedy “closest-first is final” guarantee and need a different algorithm — Bellman-Ford — which is beyond this week. Knowing that boundary is part of knowing the tool.)

Coach’s Note — Notice the through-line: BFS uses a plain queue and answers fewest hops; Dijkstra uses a priority queue and answers least weight. Same family, one upgrade to the queue. You have now seen four uses for the structures of Chapter 4 — stack for DFS, queue for BFS, priority queue for Dijkstra — which is exactly why we built them first. The structures aren’t trivia; they’re the engines the algorithms run on. Build the engine, then it powers everything.

7.8 — Modeling Discipline: From a Dataset to Vertices and Edges

Everything above assumes the graph already exists in memory. In real work, it doesn’t — it’s a CSV, a database table, a pile of references — and turning raw data into a graph is the architect’s modeling step. This is where the project lives, so let’s make it concrete.

Given a real dataset, the modeling discipline is four questions, answered in writing before any code:

1. What is a vertex? One sentence. (“A vertex is a person in the small-group roster.”) This is the most consequential choice; everything else hangs on it.
2. What is an edge — and is it directed or undirected, weighted or unweighted? (“An edge is shares a small group with, undirected and unweighted.”) Pick the cell from §7.2’s two-by-two grid.
3. Which queries do I need to answer? (“Shortest hops between two people; whether two people are connected; how many separate fellowships exist.”) The queries decide BFS vs DFS vs components.
4. Given the density and the queries, which representation? (“Sparse social data, neighbor-walking queries → adjacency list.”) The Chapter-2 cost decision, made on purpose.

The edge-list CSV is the most common real-world graph format, and it’s exactly what code/small_group_edges.csv is — one edge per line, person_a,person_b. Loading it into an adjacency list is a handful of lines:

def load_graph(path):
    adj = {}
    with open(path, encoding="utf-8") as f:
        for raw in f:
            line = raw.strip()
            if not line or line.startswith("#"):    # skip blanks and comments
                continue
            a, b = (part.strip() for part in line.split(","))
            adj.setdefault(a, set()).add(b)
            adj.setdefault(b, set()).add(a)         # undirected: both directions
    return adj

Notice the modeling decisions baked into those eleven lines: undirected (we add both directions), unweighted (we store no number), vertices are people (the strings), edges are shared groups (the rows). Change the dataset to “Maya follows Marcus” and you’d drop the second .add — directed. Change it to “distance in miles” and you’d store (b, weight) tuples — weighted. The loader is the model. Write it deliberately.

Coach’s Note — The number-one graph bug in production is a modeling bug, not an algorithm bug: someone modeled a directed relationship as undirected, or made vertices out of the wrong entity, and then ran a flawless BFS on the wrong graph. The algorithm was perfect. The model was wrong. So the answer was wrong, confidently and fast. Spend your care on the four modeling questions. The traversal is the easy, well-trodden part; the model is where the judgment — and the bugs — live.

7.9 — Common Bugs

The bugs that bite when you build and walk graphs.

Bug: Forgetting the visited set, so DFS or BFS loops forever around a cycle. Example: def visit(v): for n in adj[v]: visit(n) with no visited check — on any graph with a cycle this recurses until Python raises RecursionError (or hangs). Fix: Always carry a visited set and check membership before recursing/enqueuing. Trees can skip it (no cycles); graphs never can. This is the one line that separates tree traversal from graph traversal.

Bug: Using a Python list as the BFS queue and calling .pop(0). Example: queue = [start]; ... vertex = queue.pop(0) — each pop(0) is O(n) (shifts every element), turning an O(V+E) BFS into O(V²) silently. Fix: Use collections.deque and .popleft(), which is O(1). The exact quadratic trap from Chapter 2’s Common Bugs, now in a graph.

Bug: Marking vertices visited on dequeue instead of on enqueue in BFS. Example: popping a vertex, then adding it to visited — meanwhile the same vertex was enqueued five times by five neighbors before any of them was processed. Fix: Add to visited the instant you append a vertex to the queue. Each vertex should enter the queue exactly once.

Bug: Modeling a directed relationship as undirected (or vice versa). Example: Loading “A follows B” by adding edges in both directions, so your “who can A reach?” answer includes people A merely follows back from. Fix: Decide directed vs. undirected from the meaning of the relationship, in writing, before coding (§7.2). Directed → add one direction; undirected → add both. The loader encodes the model.

Bug: Using BFS for a weighted shortest path. Example: Finding the cheapest flight route with plain BFS — it returns fewest legs, which may cost far more than a multi-leg route. Fix: Unweighted shortest path → BFS. Weighted shortest path → Dijkstra with a heapq priority queue (§7.7). The weighting decides the tool.

Bug: Reaching for an adjacency matrix on a large sparse graph and running out of memory. Example: A 100,000-vertex social graph in a matrix needs a 10-billion-cell grid (~10 GB+), even though it has only a few hundred thousand edges. Fix: Sparse → adjacency list (O(V+E)). Reserve the matrix for dense or small graphs, or when O(1) edge lookup is the dominant query (§7.3). Check the density before you choose.

7.10 — Reps

Open the exercises for the full set. This week’s reps build the muscles the project needs: seeing the graph in a problem, storing it both ways and paying for each, and walking it with BFS and DFS until the queue-vs-stack distinction is in your fingers. AI stays OFF — Phase 1. You cannot direct an agent to choose a representation well if you have never paid the cost of choosing badly yourself.

A preview:

• Rep 1 — Read five problem statements and, for each, name the vertices, the edges, and the cell (directed/undirected × weighted/unweighted).
• Rep 4 — Turn one edge list into both representations — adjacency list and adjacency matrix — and verify them on a three-vertex triangle.
• Rep 7 — Implement BFS shortest-hops with a deque; prove it gives the true shortest by hand on a small graph.
• Rep 11 — Count connected components and explain, in two sentences, why the same DFS that answers reachability also counts islands.

Do every one. The reps are the conditioning; the project is the game.

7.11 — This Week’s Project

You’re ready for Project 7 — Model and Traverse a Network, in Project 7.

You will take a provided real-ish dataset, model it as a graph — writing down your four modeling decisions before any code — store it as an adjacency list, and implement BFS (shortest hops) and DFS (connectivity) to answer real questions about the network. The Medium tier adds the adjacency-matrix representation and makes you measure the space cost on a sparse versus a dense graph, confirming the §7.3 rule of thumb with your own numbers. The Hard tier adds a real query the dataset makes interesting — connected components, or a simple Dijkstra — plus the list-versus-matrix decision memo, with measured numbers and the conditions that would change your answer.

Like every Phase 1 project, it ends in a measurement memo. The code is half the grade; the honest accounting of which representation this dataset deserves, and why, is the architect’s half.

7.12 — Coach’s Final Word for Week 7

This week you learned to see. A route, a dependency, a fellowship, an import graph, an approval flow — all the same shape underneath, vertices and edges, and the moment you name the vertices and the edges you have done the hard part. You learned the vocabulary that lets you state precisely what kind of graph you have. You stored it two ways and paid two different prices, and you can now choose between them by density and by query instead of by habit. You walked it breadth-first with a queue for shortest hops and depth-first with a stack for reachability, and you saw that one structure swap turns one into the other. And you learned that when the edges carry weight, the queue becomes a priority queue and BFS becomes Dijkstra.

You did not memorize algorithms. You learned to recognize which of a handful of questions a problem is really asking, and to reach for the structure that answers it.

If the queue-versus-stack symmetry felt slippery: that’s the gap. Write both loops side by side in the project, change only the data structure, and watch breadth become depth. Close it.

Paul saw the church as a body — many members, individually members one of another, no part able to say to another “I have no need of you.” That is a connected graph, and a richly connected one, and the health of the body is, in graph terms, exactly its connectedness: that no member is an island, that there is a path of love and need between every part and every other. When you ran connected components and found the pair cut off from the rest, you found, in the smallest possible key, the thing the church is always watching for — the member falling through the cracks, the part no path reaches. The architect’s tool and the pastor’s concern, the same shape. See the graph. Then go build the bridge.

See you on Monday.

Up next: Read the exercises and complete every rep. Then open Project 7 and model your network. After that, Chapter 8 — concurrency, threads, and the Phase 1 midterm, where many hands learn to work as one without chaos.

Previously: Chapter 6 — trees: when hierarchy is the shape, and the recursion that walks them (which became this week’s DFS the moment the structure was allowed to loop back on itself).