Graphs

Every structure so far restricted how things connect: the list's single file, the tree's strict hierarchy. The graph drops all restrictions. A graph is just two sets: vertices, the things, and edges, the connections between pairs of them. Cities and roads. People and friendships. Machines and network links. Software packages and their dependencies. And, most important for this Academy, the basic blocks of a program and the jumps between them, the control flow graph you met in Level 5, which is the load-bearing data structure of both compilers and reverse-engineering tools.

• Undirected graph: edges are mutual, a friendship. If A connects to B, B connects to A.
• Directed graph: edges have direction, a follow, a one-way street, a jump from one basic block to another.
• Weighted graph: each edge carries a number, distance, cost, latency, and algorithms optimize over the weights.
• Path: a sequence of edges from one vertex to another. Cycle: a path returning to its start, the thing trees forbid.
• Degree: how many edges touch a vertex. V and E: the standard names for the vertex and edge counts, and every graph cost is quoted in them.

A subway map is a graph you already read fluently: stations are vertices, track segments are edges, and the two questions you ask of it, can I get there from here, and what is the fewest stops, are literally the two classic graph problems, reachability and shortest path. A tree is just a graph on its best behavior: connected, no cycles, one path between any two vertices. Graphs allow shortcuts, dead ends, and round trips, which is exactly why they can model the real world and why exploring them takes actual algorithms.

Storing a graph: the first real decision

Two standard representations exist, and choosing is a pure complexity exercise, laid out in Open Data Structures' graphs chapter. The adjacency matrix is a V by V grid of booleans: cell row a, column b answers is there an edge from a to b in O(1). The price is V squared cells no matter how few edges exist. The adjacency list gives each vertex a list of its neighbors: total storage O(V + E), and walking a vertex's neighbors costs only its degree, but asking is a connected to b means scanning a's list. The decider is density. Real networks are overwhelmingly sparse, E nowhere near V squared: a million-user social network where people average 200 friends has two hundred million list entries, while its matrix would need a trillion cells, nearly all storing the word no. Watch the arithmetic.

The factor of 2 in the list count is worth catching: an undirected edge appears in both endpoints' lists, so E edges occupy 2E entries, a bookkeeping fact the challenge below turns into a bug hunt. The matrix earns its V squared when graphs are dense or when O(1) edge tests dominate the workload, and its grid shape unlocks algebraic tricks, entire algorithms run as matrix operations. But the default in practice and in the rest of this lesson is the adjacency list, because the traversal costs that follow are quoted as O(V + E), and only the list representation actually delivers them.

Exploring: BFS and DFS

The universal graph task is traversal: starting from a vertex, visit everything reachable. Two algorithms do it, and the stacks and queues lesson already gave away their souls: the only difference between them is which structure holds the frontier, the set of discovered-but-not-yet-explored vertices. Breadth-first search, BFS, uses a queue: explore the oldest discovery first, which ripples outward in rings, all vertices one edge away, then two, then three. That ordering is a theorem in disguise: BFS reaches each vertex by a shortest possible edge path, so it computes shortest paths in unweighted graphs, the subway question, answered. Depth-first search, DFS, uses a stack, or equivalently recursion, the call stack doing the job implicitly: plunge down the newest discovery, hit a dead end, backtrack. Its retreating order encodes dependency structure, which is why DFS underlies cycle detection and topological sorting, the algorithm that orders build steps so prerequisites come first.

Both run in O(V + E) with adjacency lists: every vertex enters and leaves the frontier once, every edge is examined a constant number of times, and a visited set prevents the cycles from spinning the search forever. Forgetting that visited set is the classic graph bug: in any graph with a cycle, the frontier refills endlessly. Linear in the size of the network is remarkably cheap, which is why both searches are the opening act of nearly every graph algorithm in 6.006, run first, then refined.

The graph you will actually fight over

For protection work, one graph towers over the rest: the control flow graph, vertices are basic blocks of straight-line code, directed edges are the possible jumps between them. You saw its picture in Level 5; you now own its theory. A decompiler recovering readable structure is running graph algorithms, finding loops as cycles, nesting as domination structure. Control flow flattening, Level 6's heavyweight transform, is a deliberate attack on that analysis: it rewires a readable graph into a flat star around one dispatcher, hiding the true edges inside runtime state, forcing the analyst from cheap static graph queries into expensive dynamic exploration. And the analyst's answer, tracing execution to rebuild the real edge set, is graph traversal again, BFS and DFS wearing work clothes. Both sides of the obfuscation war are, quite literally, doing graph theory at each other.

A graph is vertices plus edges, with direction and weights optional. Sparse graphs, which is most of them, want adjacency lists at O(V + E) storage; matrices pay V squared for O(1) edge tests. BFS explores with a queue and finds shortest unweighted paths; DFS explores with a stack and exposes cycles and dependency order; both run in O(V + E) and both power the control flow analysis at the heart of deobfuscation.

Frequently asked questions