Graph Algorithms
Topological sort, MST, and Bellman-Ford
Ordering, spanning, and negative weights
Dijkstra answered one graph question - shortest paths with non-negative weights. Three more questions round out the essentials, and each has a clean, greedy-ish answer. Topological sort puts a directed acyclic graph in dependency order (do this before that). Minimum spanning tree connects every node for the least total weight. Bellman-Ford finds shortest paths where Dijkstra breaks - with negative edges - and, as a bonus, tells you when no shortest path exists at all. All three are built from the same two verbs you already know: peel and relax.
Peel, merge, relax
A topological sort takes a DAG - a directed graph with no cycles - and lines the nodes up so every edge points forward. The trick is Kahn's algorithm: a node with in-degree zero depends on nothing, so it is safe to output; peel it off, delete its out-edges, and some neighbor's in-degree drops to zero next. Repeat until the graph is empty. If you ever get stuck with nodes left but none at zero, the graph had a cycle.
Peeling a DAG
Think of build steps, course prerequisites, or make targets: each node waits on the ones pointing into it. In-degree is exactly "how many prerequisites are still unmet." Output any node whose count has hit , decrement its dependents, and a valid order falls out. When several nodes sit at at once, any of them is a legal next pick - that is why a DAG usually has many valid topological orders, not one.
A minimum spanning tree works on an undirected, weighted graph: choose a subset of edges that connects all nodes with no cycle (a tree, so exactly edges) and the smallest possible total weight. Kruskal's method is pure global greed - sort every edge by weight and add each one in turn, skipping any edge whose two endpoints are already connected, because that edge would only close a cycle. The "already connected?" test is precisely the union-find structure from earlier: find(u) == find(v) means reject, otherwise union(u, v) and keep it.
Why Kruskal is safe
The engine is the cut property: split the nodes into any two groups, and the lightest edge crossing that divide belongs to some MST. Kruskal considers edges lightest-first, so whenever it adds an edge it is the cheapest link joining two still-separate components - a crossing edge of the cut between them. Every accepted edge is safe by this rule; every rejected edge would have both ends on the same side, adding a redundant cycle. A cousin, Prim's algorithm, grows one tree outward with a priority queue (much like Dijkstra) instead of sorting all edges - same tree, different bookkeeping.
Bellman-Ford attacks single-source shortest paths without Dijkstra's catch. It makes no greedy commitment: it simply relaxes every edge, then does it again, times over. Because a shortest path can only touch each node once, it spans at most edges - so full sweeps are enough to let the best distance ripple all the way out, one edge per round in the worst case.
Relax V-1 times, then check
Relaxation is the same one move as in Dijkstra - for an edge of weight :
After rounds, is correct for every node whose shortest path uses at most edges. Simple paths use edges, so rounds finish the job - and negative weights are fine, because nothing is ever "settled" and locked. Then run one extra round: if any distance still drops, a path just used edges, which means it repeated a node - a cycle whose total weight is negative. Shortest paths are then undefined (loop forever to go lower), and Bellman-Ford reports the negative cycle instead.
See all three run
One canvas, three tabs - each algorithm on a small fixed graph it suits. Topological sort peels off zero-in-degree nodes and lays them on a line. MST steps Kruskal: edges come sorted, union-find turns accepted edges teal and strikes out any that would close a cycle. Bellman-Ford relaxes all edges round by round; add the back-edge to watch a negative cycle get caught on the check round. Step through, or press Play.
Ready queue - in-degree 0, pick alphabetically
Topological order - every edge points forward along this line
Count each node's in-degree - the arrows pointing in. Two nodes start at 0 (A and B depend on nothing), so either may go first.
The same two verbs
Notice how little machinery is really at play. Topological sort peels - it repeatedly removes a node with no unmet dependency. Kruskal and Bellman-Ford relax in different guises: Kruskal keeps the cheapest edge that improves connectivity, Bellman-Ford keeps the cheapest path that improves a distance. Dijkstra is Bellman-Ford with a greedy shortcut that only holds when weights are non-negative. Learn peel and relax, and the whole graph-algorithm zoo stops looking like a zoo.
The code
Kahn's topological sort and Bellman-Ford are both a dozen lines. (Kruskal is just: sort the edges, then union(u, v) each one whose find(u) != find(v) - the disjoint-set from earlier, verbatim.)
from collections import deque
def topo_sort(nodes, edges): # edges: list of (u, v)
indeg = {n: 0 for n in nodes}
adj = {n: [] for n in nodes}
for u, v in edges:
adj[u].append(v); indeg[v] += 1
ready = deque(n for n in nodes if indeg[n] == 0)
order = []
while ready:
u = ready.popleft() # any zero-in-degree node is safe
order.append(u)
for v in adj[u]:
indeg[v] -= 1 # u placed; v loses a dependency
if indeg[v] == 0:
ready.append(v)
return order if len(order) == len(nodes) else None # None => a cycle
def bellman_ford(nodes, edges, src): # edges: (u, v, w), w may be < 0
dist = {n: float("inf") for n in nodes}
dist[src] = 0
for _ in range(len(nodes) - 1): # V-1 rounds
for u, v, w in edges:
if dist[u] + w < dist[v]: # relax every edge
dist[v] = dist[u] + w
for u, v, w in edges: # one extra round: still improving?
if dist[u] + w < dist[v]:
raise ValueError("negative cycle") # a V-th drop = a cycle
return distCheck yourself
In a topological sort of a DAG, which node is always safe to output next?
Only one of these gives correct shortest paths when some edge weights are negative. Which?
Recall: how does Kruskal build an MST, and what stops it from adding an edge?
Retrieval practice on the cut property and union-find connection. Try to state it, then check.
Lock it in
- Topological sort (Kahn's) orders a DAG by repeatedly outputting any in-degree-zero node; if nodes remain but none sit at zero, the graph has a cycle.
- Kruskal builds an MST by adding edges lightest-first, skipping any whose endpoints are already connected (union-find); the cut property proves each pick safe, and it stops at edges.
- Bellman-Ford relaxes every edge times, so it handles negative weights; one extra round that still improves a distance reveals a negative cycle.
- All three reduce to two verbs, peel and relax - and Dijkstra is just Bellman-Ford with a greedy shortcut valid only for non-negative weights.
Primary source
Work through all three with Abdul Bari - Graph algorithms (Topological sort, MST, Bellman-Ford), then build your own weighted graphs and watch Kruskal and Prim grow a spanning tree edge by edge at VisuAlgo - Minimum Spanning Tree.
Ask your teacher
Here is the payoff that makes this lesson matter for the LLM track: topological sort is exactly how a neural network runs. A network is a computational graph - nodes are operations, edges are data dependencies - and the forward pass visits those nodes in topological order, computing each only after its inputs exist. Then backprop visits them in reverse topological order, so every node's gradient is ready before the nodes feeding it need it. That bridge is traced in topological sort and DAGs to backpropagation in the LLM course. Training, at its core, is graph algorithms. Want to see the same DAG driving both a forward pass and a backward pass, side by side? Ask, and I'll build the follow-up.