The algorithm for topological sort, in CLRS goes as follows :
- call DFS(G) to compute finishing times v.f for each vertex v
- as each vertex is finished, insert it onto the front of a linked list
- return the linked list of vertices
Let's we have a directed graph, as in the figure here:
If we start DFS from arbitrary vertices, we get different topological orders -- for instance, if the top level DFS loop goes through vertex
b first, then
i and finally
a, one possible ordering of finishing times (largest to smallest) is :
(a), (i), (d,h,l,k,j), (b,c,f,e,g)
where each grouped term within the parenthesis indicates one iteration of DFS from the starting vertex.
If the vertices are taken in a different order, say
a first, then
d, and then
i, the order of finishing times becomes:
(i), (d,h,l,k,j), (a,b,c,f,e,g).
If these were to indicate valid orders of events, how can they both be valid topological orders? The sorting algorithm does not mention any specific order of vertices to use in DFS.