An acyclic digraph can be laid out in a line so that every arc points forwards. Two algorithms produce such a line: reverse finishing order from one depth-first walk, and repeatedly removing a vertex nothing points into. They generally disagree, and both are right, because the order is usually not unique. The lab answers uniqueness with a number by enumerating every valid order there is.
Core ideas
The hard idea is that two correct algorithms disagreeing is not a bug. The other two are the existence condition and the way uniqueness is settled.
If the vertices can be lined up with every arc pointing forwards then a cycle would have to return to a vertex already passed, which would need an arc pointing backwards. Conversely, if there is no cycle then one depth-first walk has no back arc, and listing the vertices by decreasing finish time is a valid order. So existence is not a separate question from acyclicity: it is the same question.
Reverse finishing order comes out of the depth-first walk at no extra cost. Kahn's method instead keeps the in-degrees, emits any vertex whose in-degree has reached 0, and decrements its successors. On the lab's opening task graph the first returns 2 1 3 5 4 6 and the second returns 1 2 3 4 5 6. The panel checks each one arc by arc, and both pass.
“Is the order unique?” has a numerical answer: how many valid orders are there. The lab enumerates them all. The opening graph has 4; a chain of five vertices has 1, which is what uniqueness looks like; a diamond has 2; five vertices with no arcs at all have 120. A graph with a cycle has 0, and the enumeration reports that as the same fact the walk reports as a back arc.
The material
The definition, the existence theorem, the two algorithms with their counts, and what the enumeration is for.
A topological order of a digraph is a listing of all its vertices such that for every arc (u, v), u appears before v. A digraph with such a listing is often drawn left to right, which makes the condition visible: no arc points leftwards.
A digraph has a topological order if and only if it is acyclic.
If a topological order exists and v1, v2, ..., vk, v1 is a cycle, then each arc of the cycle forces its tail earlier than its head in the listing, so v1 appears strictly before itself. That is impossible, so there is no cycle.
If the digraph is acyclic, run one depth-first walk. It has no back arc, so for every arc (u, v) the head v is either discovered inside u and finished before it, or already finished when the arc is examined. Either way f[v] < f[u]. Listing the vertices by decreasing f therefore puts every tail before its head.
□
The proof is also the algorithm, which is why the first method costs nothing beyond the walk: sort by finish time, or equivalently push each vertex onto a stack as it closes and read the stack off. The lab reports 6 vertex visits and 6 arc reads on the opening graph, the same Θ(V + E) the walk itself costs.
On the opening graph 1>3, 2>3, 3>4, 3>5, 4>6, 5>6 the starting in-degrees are 0, 0, 2, 1, 1, 2, two vertices are in the queue at once, and the method emits 1 2 3 4 5 6 with 4 queue pushes, 6 pops and 6 arc reads. The walk's answer on the same graph is 2 1 3 5 4 6. Both are checked arc by arc in the panel and both pass, and the disagreement is not a defect in either.
For that graph the lab enumerates every valid order and finds 4: 1 2 3 4 5 6, 1 2 3 5 4 6, 2 1 3 4 5 6 and 2 1 3 5 4 6. Kahn's answer is the first and the walk's answer is the last. The freedom is exactly the two independent starts and the two independent middles, and 2 times 2 is 4.
The enumeration is a real search over all orders, not a formula, so it is refused rather than run slowly above the size it can finish: nine vertices is declined with a message naming the cap, and the reason is that eight vertices with no arcs already have 8! = 40 320 orders. Where it does run, the number it prints is a fact about every order rather than about the one produced.
A chain of five vertices has exactly 1 valid order; a diamond has 2; five vertices with no arcs have 5! = 120. The chain is the shape uniqueness needs: there must be an arc between each consecutive pair in the order, because two vertices with no path between them can always be swapped. So uniqueness is equivalent to the order being a Hamiltonian path of the digraph, which is a much stronger condition than acyclicity.
A cycle shows up twice, by two different mechanisms, and the lab prints both. On 1>2, 2>3, 3>1, 3>4 the depth-first walk finds a back arc and returns no order; Kahn's queue starts empty, because every one of the first three vertices has in-degree 1, and it emits nothing at all. The enumeration independently returns a count of 0. Three witnesses, one cause.
The measured counts are worth putting beside the bound. Kahn's method on the opening graph did 4 pushes, 6 pops and 6 arc reads, which is V pops and E reads. That is Θ(V + E) for this graph. The bound is the claim that it is Θ(V + E) for every graph, and the argument is that each vertex enters the queue at most once — it enters when its in-degree reaches 0, and the in-degree only ever decreases — and each arc is read exactly once, when its tail is emitted.
Interactive
A reverse postorder and an in-degree queue; on a cycle, neither exists and both say so
Method
Produce one, check it, and only then ask whether it was the only one.
If a depth-first walk is being run anyway, the order is free: push each vertex as it closes. If the in-degrees are already maintained, Kahn's method is free instead. Neither is better; they cost the same and produce different answers.
For every arc, confirm the tail's position is lower than the head's. This is E comparisons and it catches an off-by-one in the emission order that a drawing will not. The lab does exactly this and reports a verdict per algorithm.
Neither algorithm should be made to fail silently. A walk that stops with a back arc has the cycle in hand: it is the tree path from the head down to the tail plus that arc. Kahn's method instead leaves you the set of vertices never emitted, which is everything on or downstream of a cycle.
Two correct algorithms agreeing is not uniqueness; on the diamond they can agree and there are still two orders. Enumerate where the graph is small enough, and where it is not, check the much simpler equivalent condition: is there an arc between every consecutive pair of the order you produced?
The dependencies are 1>3, 2>3, 3>4, 3>5, 4>6, 5>6: two things must happen before 3, then 4 and 5 may happen in either order, then 6.
The two answers differ in both places the graph allows them to. Kahn's emitted 1 before 2 because 1 was pushed first; the walk finished 2 last because it restarted there. Neither choice is forced by an arc, which is precisely why the enumeration finds four orders and not one.
Notice what the enumeration is being used for. It is not a third algorithm for producing an order — it is far too expensive for that. It is the only way on this page to turn “the order is not unique” from an impression into a number, and the number is what the lesson's third concept is about.
For a faded rehearsal, add the arc 4>5 and predict the new count before running it. The supplied first move is this: the only freedom left between 4 and 5 is removed, so the two middle choices collapse to one while the two starting choices survive. Say what the count becomes, then add 2>1 as well and say what it becomes then.
You should be able to run Kahn's method with the in-degree table by hand, read a topological order off one walk's closings, check a candidate order arc by arc, and say what uniqueness would require of the graph rather than inferring it from two algorithms agreeing.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.