Card 06/ 08
Topological Order From Depth-First Finishing Times
A vertex finishes only after everything it leads to, so the finishing order reversed points every edge forwards.
Depth-first search gives a topological order with no in-degrees at all: record each vertex as it finishes, then reverse the list. This card runs that on the topic's graph, explains why the reversed list points every edge forwards, and compares it with Kahn's order.
A vertex finishes when depth-first search has explored everything reachable from it and turns it black; listing vertices in that order is a post-order. The search starts from each vertex not yet visited, in alphabetical order, and takes neighbours in alphabetical order. The steps below are from a run, one per finish, with the path on the stack, the colours, and the finished list.
Depth-first search on the topic's graph, one step per vertex finished; reversed, the finished list F A E B C D gives D C B E A F
Finish F
The search starts at A and follows A->F. F has no outgoing edges, so it finishes first.
stack: A
colours: A grey, B white, C white, D white, E white, F black
finished: FFinish A
A has no other edges, so it finishes. Nothing more is reachable from A.
stack: (empty)
colours: A black, B white, C white, D white, E white, F black
finished: F AFinish E
B is the next white vertex. Its neighbours are E and F, and E goes first and finishes at once.
stack: B
colours: A black, B grey, C white, D white, E black, F black
finished: F A EFinish B
F is already black, so B finishes.
stack: (empty)
colours: A black, B black, C white, D white, E black, F black
finished: F A E BFinish C
C's only edge goes to B, which is black, so C finishes as soon as it starts.
stack: (empty)
colours: A black, B black, C black, D white, E black, F black
finished: F A E B CFinish D
D's edges go to A and B, both black. D finishes last.
stack: (empty)
colours: A black, B black, C black, D black, E black, F black
finished: F A E B C DReversed, F A E B C D becomes D C B E A F, and the run checked that all six edges point forwards in it. Unreversed, the finishing order points every one of the six edges backwards, which is the mistake to avoid: the finishing order is the topological order read from the end.
The reason is that, in a graph with no cycle, a vertex finishes only after every vertex it has an edge to. For an edge u->v, when the search looks at v from u, v is either white, and is explored and finished before u, or already black, and finished earlier. It cannot be grey, because a grey v would mean a path from v back to u, and with the edge u->v that is a cycle. So v always finishes before u, and reversing puts u first.
Kahn's algorithm gave C D A B E F on the same graph, and depth-first search gives D C B E A F. Both are valid, and both cost O(V + E). Kahn's algorithm needs no recursion and reports a cycle by its count; depth-first search reports a cycle by meeting a grey vertex, and suits code that already has a depth-first search in it.
← → move through sections and cards