Why does a valid recalculation order exist for a spreadsheet only when its cell-reference graph is acyclic?

## The model A sheet of formulas is a **directed graph**. Each cell is a node. For every formula, draw an edge from each cell it reads to the cell that reads it: `A1 -> B1` means "A1 must be computed before B1". The graph carries no geometry, no rows, no columns — only the dependency relation. A **recalculation order** is a list of all the cells such that every cell appears after all the cells its formula reads. In graph vocabulary that is a **topological order**: a linear arrangement of the nodes in which every edge points forward, from an earlier position to a later one. ## Why a cycle makes it impossible Suppose three cells reference each other in a ring: the first reads the second, the second reads the third, the third reads the first. Follow the edges: whatever order you write down, the first cell must come before the second, the second before the third, and the third before the first — so the first must come before itself. "Before" is a strict order, and no element is strictly before itself. The requirement is contradictory, so *no* list of cells satisfies it. This is not an implementation limitation you can code around; it is a property of the relation. A self-reference is the smallest instance: a cell whose formula reads itself is a cycle of length one, and it fails for the same reason. ## Why acyclicity is enough The other direction is what makes the concept useful. Claim: a finite directed graph with no cycle always has at least one node with **in-degree zero** — no incoming edges. Proof sketch: pick any node and walk backwards along incoming edges. Each step moves to a predecessor. If you could always keep stepping, then after more steps than there are nodes you must land on a node you already visited, and the walk between the two visits is a cycle. Since there is no cycle, the walk must stop, and it stops exactly at a node with no incoming edges. That gives a construction: emit an in-degree-zero cell, delete it and its outgoing edges, and repeat. Deleting a node from a graph with no cycle leaves a graph with no cycle, so the argument applies again, and the process empties the graph. The sequence of emitted cells is a valid recalculation order. So the condition is exactly right in both directions: **an order exists if and only if the graph is a directed acyclic graph (DAG)**. The construction is also the algorithm, and with an adjacency list plus an in-degree count per node it runs in O(V + E) time and O(V) extra space for V cells and E references — linear in the size of the sheet. ## The traps **"The graph is connected, so an order exists."** Connectivity is irrelevant. A sheet split into five unrelated islands of formulas is still perfectly orderable — concatenate an order for each island. Conversely a single tightly connected ring of three cells has no order at all. The property that matters is the absence of cycles, nothing else. **"Some cell has no references, so we can just start there."** Having a starting point is necessary but not sufficient. A sheet can have a hundred independent input cells and still contain one three-cell ring buried in the middle; the ring is unorderable regardless of how many clean starting points exist elsewhere. **"A cycle just means you pick an arbitrary starting cell and go around."** That is a different computation, not an ordering. Some engines do offer *iterative* recalculation: they seed the cells in the cycle with values and sweep repeatedly a bounded number of times, hoping the values settle. That is a numerical fixed-point approximation with a convergence question attached, and it produces a result no dependency order justifies. Do not describe it as a topological order. **"Then everything must be recomputed every time."** No. The order also tells you the *blast radius* of an edit: when one cell's formula or value changes, only the cells reachable from it along the edges can be affected. Take that reachable subgraph and order just it — the cost is linear in the touched part, not in the whole sheet. ## Why interviewers ask this It is the smallest question that checks whether you can move between a concrete requirement ("compute each cell after its inputs") and the graph property that decides whether the requirement is satisfiable at all. The same shape recurs everywhere dependencies exist: build steps, package installs, task pipelines, data migrations. Recognising "this is a DAG question" is most of the work; the ordering algorithm itself is a dozen lines.