Metadata Card

• Prerequisites: Chapter 5 — Relations and Functions
• Estimated time: 50 minutes
• Core difficulty: Intermediate
• Completion marker: Master graph representation methods, understand graph traversal and connectivity, grasp the idea of shortest paths

Your Progress

In the previous tower, you learned counting. In the second room of the Combinatorics Tower, the walls are covered with interwoven patterns of dots and lines. The Librarian traces a path with his finger: "From one point to another, how many paths are there? This is the mathematics of maps."

Your Task

How does "friend of a friend" get discovered in social networks? How does a map app calculate navigation routes? How do task dependencies in a scheduling system get modeled? These questions share the same mathematical structure — a graph. It's simply a collection of "nodes" and "edges," yet it can describe internet topology, program control flow, CI/CD pipeline dependencies, and all state machine transitions.

Chapter Layers

• Required reading: Graph definition and representation, depth/breadth-first search, shortest paths
• Optional reading: Minimum spanning trees, topological sort

Breakthrough · Origin Story

You need to schedule a project's build order. Module A depends on B, B depends on C, D depends on B and E. You need to find the order of "what to compile first," and also determine whether compilation is even possible. After ten minutes of manual scheduling, you suspect there might be a deadlock. What you need is a systematic method — the topological sort provided by graph theory.

Graph definition: A graph G = (V, E), where V is the set of nodes (vertices) and E is the set of edges. An edge connects two nodes.

Concept	Definition	Programming Equivalent
Directed graph	Edge has direction, a→b ≠ b→a	Function call relationships
Undirected graph	Edge has no direction	Social network friendships
Weighted graph	Edge has a numeric value (weight)	Road distances on a map
Adjacency matrix		V
Adjacency list	Each node has a list of neighbors	Sparse graphs (most practical cases)

The choice of storage affects algorithm efficiency. In most practical graphs, the number of edges E is far less than the square of the number of nodes V (sparse graphs), where adjacency lists are far superior in both memory and traversal efficiency.

Graph traversal: The method of visiting all nodes in a graph.

Depth-First Search (DFS): Follow one path all the way, then backtrack. Recursive implementation is a natural fit:

DFS's recursive structure maps directly to the function call stack — when your programming language executes a recursive function, the low-level mechanism is exactly the same. The crawler, garbage collector mark phase, and maze solver you write all run this pseudocode at their core.

DFS(v):
  mark v as visited
  for each neighbor u of v:
    if u is not visited then DFS(u)

DFS is useful in topological sort — the order of post-order traversal is the reverse of the topological order.

Breadth-First Search (BFS): Expand outward layer by layer. Implemented with a queue. BFS always finds the shortest path (in unweighted graphs).

BFS appears repeatedly in operating system task scheduling, message queue distribution, and social network recommendations. Each layer of expansion corresponds to a queue, and the FIFO nature of the queue guarantees the shortest path — which is also why message middleware's topic matching algorithms resemble BFS.

BFS(s):
  initialize queue Q, enqueue s
  mark s as visited
  while Q is not empty:
    v = Q.dequeue()
    for each neighbor u of v:
      if u is not visited then mark and enqueue

Shortest path: In weighted graphs, Dijkstra's algorithm is the standard. Starting from the source, maintain the current shortest distance to each node, using a priority queue to select the unprocessed node with the smallest distance.

Topological sort: Order the nodes of a directed acyclic graph (DAG) such that for every directed edge, the start node appears before the end node. If the graph contains a cycle (circular dependency), topological sort is impossible — your build system will report an error.

Common Pitfalls

• Forgetting to check if the graph has cycles. DFS and BFS run happily on acyclic graphs but loop infinitely when encountering cycles. You need to detect cycles before traversal.
• Confusing algorithm choices for sparse vs. dense graphs. Dijkstra with adjacency matrix O(V²) is faster on dense graphs; adjacency list + priority queue O(E log V) is faster on sparse graphs. There is no universally optimal approach.
• Thinking graphs are "only for computer science." The origin of graph theory — the Seven Bridges of Königsberg problem — predates computers by over two hundred years.

Challenge Questions

• Draw the DAG of your project's build dependencies and produce the topological sort result.
• Traverse the same graph with DFS and BFS, and compare the differences in output order.
• Implement an undirected graph in Python using adjacency lists, and write an is_connected() method to check connectivity.

Traveler's Notes

A graph is mathematics drawn out. Nodes are the entities you care about, edges are the connections between them. Traversal, connectivity, ordering — these are the underlying models you work with every day in social networks, maps, and build systems.

→ Next stop: Graphs give you the structure of relationships. But what if these relationships aren't deterministic? "The probability of rain tomorrow is 70%." Next, we enter the realm of probability.