Run Kahn's algorithm on the same graph ten times, and you might get ten different topological orderings. That sounds like a bug. It's not.
Every time Kahn's dequeues a node from the queue, there might be multiple ready nodes waiting. Which one gets dequeued first? That depends on the queue's internal order -- FIFO, alphabetical, random. The algorithm is correct no matter which ready node you pick. All choices lead to valid topological orderings, just different ones.
You've probably noticed this already. In Module B, when you predicted the ripple cascade, there were moments where two nodes became ready simultaneously. You picked one. You could have picked the other. Both would have been correct.
But how MANY valid orderings does a graph have? And what determines the count? Is a graph with 50 valid orderings somehow “looser” than one with 2? Let's find out by doing what we always do: building and exploring.
Think of it like a university course catalog. Some courses have hard prerequisite chains: Calc I before Calc II before Calc III. That chain has exactly one valid order. But if you also need to take History 101 and Art 101, neither of which depends on the other or on any Calc course, suddenly the number of valid semester plans explodes. You can interleave those electives anywhere in your schedule. Each independent course multiplies the number of valid plans. The shape of the dependency graph determines your scheduling freedom.
Here's a 6-node DAG. Your challenge: find 4 distinct valid topological orderings. Each time you build one, it gets saved. If you accidentally build a duplicate, the system catches it and asks you to try a different sequence.
At each step, the ready nodes pulse — these are the ones whose predecessors are all placed. You choose which ready node goes next. Different choices at the branching points produce different orderings. After finding 3, you'll predict how many more exist.
Every ordering you found satisfies all the dependency constraints. The constraints determine what MUST come before what — everything else is free choice. When two nodes are simultaneously ready with no edge between them, you can place them in either order. That branching point is where the ordering count multiplies.
The total number of valid orderings for a graph is determined by how many of these “free choice” moments exist during the sorting process. A graph where every step has exactly one ready node (a total chain) has exactly 1 ordering. A graph where every step has multiple choices (lots of independent nodes) has many. The ordering count is a measure of the graph's parallelism.
Here's one of the orderings you found. Between each pair of adjacent nodes, you'll check: can these two swap positions and still produce a valid ordering?
The answer depends on one thing: is there a directed edge between them? If yes, they're constrained — swapping would violate that dependency. If no, they're free — the graph doesn't care which comes first.
A and B swap positions and still be valid?You've discovered the underlying rule. Two adjacent nodes in a topological ordering can swap if and only if there's no edge between them. No edge means no dependency constraint. The swap freedom at each position directly corresponds to the absence of edges — and the more swappable pairs, the more valid orderings exist.
This gives you an intuition for why some graphs have few orderings and others have many. A total chain (every node constrained by an edge to its neighbor) has zero swappable pairs and exactly one ordering. A set of independent nodes (zero edges) has every pair swappable and n! orderings. Real graphs fall somewhere in between, and the ordering count reflects exactly how constrained the structure is.
You've discovered the pattern. Two adjacent nodes can swap if and only if there's no edge between them. No edge means no dependency constraint, which means the graph doesn't care which one comes first.
This has a beautiful implication for the number of valid orderings. A total chain — A before B before C before D, with edges between every consecutive pair — has exactly ONE valid ordering. Every adjacent pair is constrained. No swaps possible. But a diamond — one source, two independent middle nodes, one sink — has TWO valid orderings. The middle nodes can appear in either order because there's no edge between them.
Take it further. Four completely independent nodes with zero edges: 4! = 24 orderings. Every permutation is valid because nothing constrains anything.
The number of valid topological orderings measures the graph's “parallelism.” A highly sequential graph (long chain) has few orderings. A highly parallel graph (many independent nodes) has many. When you're scheduling tasks on multiple processors, the number of valid orderings tells you how much flexibility you have. A graph with only 1 valid ordering means every task must run in sequence — no parallelism possible. A graph with 24 orderings has maximum scheduling freedom.
Every node constrained — one valid order
This also explains why Kahn's and DFS might produce different orderings on the same graph. They're both valid. They just make different arbitrary choices at the branching points where multiple nodes are simultaneously ready.
DFS takes a different approach: instead of tracking in-degrees, it assigns finish times. Scrub through the traversal — nodes turn black in reverse topological order.
Start DFS at A (turn gray).
In compiler theory, this matters for instruction scheduling. The compiler topologically sorts the data dependency graph of instructions. The number of valid orderings determines how much room the scheduler has to reorder instructions for pipeline efficiency. More orderings = more optimization opportunities. Fewer orderings = the hardware pipeline is constrained by data dependencies.
You've seen that multiple valid orderings exist and explored why. But in practice, you often want a specific ordering — lexicographic for deterministic output, reverse for scheduling heuristics. The algorithm stays the same. Only the tie-breaking changes.
Fill in the blanks to see how swapping the data structure that holds ready nodes controls which valid ordering Kahn's algorithm produces. Each blank connects to the branching points you discovered in OrderingExplorer — the moments where multiple nodes were ready and you chose which went first.
Three graphs, side by side. Each has 4 nodes but very different structures. For each one, predict the number of valid topological orderings before seeing the answer.
The gradient from 1 to 2 to 24 makes the relationship vivid. Each removed edge doesn't just add one ordering — it can multiply the count. The chain is maximally constrained (1 ordering). The diamond relaxes one pair (2 orderings). Full independence is maximally free (24 orderings). Real dependency graphs live somewhere on this spectrum, and the position tells you exactly how parallel your problem is.
Three tasks: dual ordering, edge constraints, and parallelism reasoning.