Topological sort and DAGs to backpropagation

A neural network is a computational DAG: the forward pass topologically sorts it, and backprop replays that very sort in reverse to hand every node its gradient - just in time.

Two lessons you have already met turn out to be the same lesson. In Topological sort, MST, and Bellman-Ford you learned to topologically sort a DAG - order a directed acyclic graph so every edge points forward, so nothing is processed before its dependencies. In Backpropagation you built backpropagation - one reverse sweep that hands every weight its gradient. Here is the punchline that makes training a network feel inevitable rather than magical: backprop is topological sort run in reverse over a computational graph. The forward pass is a topological sort; the backward pass is its reverse. That is the whole engine behind every model you have studied.

A network is a DAG of operations

Before you can differentiate a computation, you rewrite it as a computational graph: break the whole thing into elementary ops, each a node whose edges are its data dependencies. An edge $x\to y$ means “$y$ is computed from $x$” - so $x$ must come first. Because there are no cycles, a topological order always exists: line the nodes up so every edge points forward, and you can evaluate left to right without ever meeting an unfilled input. Our toy expression takes three inputs and, crucially, reuses one intermediate value:

Forward is topological order; backward reverses it

Press ▶ Forward to fill every node's value in topological order (inputs first, loss last), then ◀ Backward to watch the gradient flow back in reverse topological order - each edge multiplying in its local derivative as it goes. Or walk it with Next. Watch node $e$: on the way back it collects a gradient from $p$, then a second one from $q$, and the two accumulate. Click any node to inspect its local derivatives and the chain rule that assembles its gradient. Drag a slider and everything recomputes live.

The same idea, in code

This is what a framework does automatically, but by hand it is a dozen lines with the shape you just watched: forward in topological order, then backward in reverse, gradients starting at zero and accumulating with +=.

# --- forward: evaluate in topological order (inputs first, loss last) ---
a, b, c = 2.0, 3.0, 1.0
e = a * b            # 6.0   shared node: feeds BOTH p and q
p = e + c            # 7.0
q = e * c            # 6.0
L = p + q            # 13.0  the loss (graph sink)

# --- backward: reverse topological order, gradients accumulate from 0 ---
gL = 1.0              # seed dL/dL
gp = gL * 1            # + node copies the gradient through
gq = gL * 1
ge  = gp * 1           # from p = e + c   (local d/de = 1)
gc  = gp * 1
ge += gq * c          # from q = e * c   ACCUMULATE at shared e
gc += gq * e
ga  = ge * b          # from e = a * b   (times swaps the other input)
gb  = ge * a
# ge = 2.0, gc = 7.0, ga = 6.0, gb = 4.0

Check yourself