Different topologically sorted order based on DFS vertex ordering

Question

The algorithm for topological sort, in CLRS goes as follows :

1. call DFS(G) to compute finishing times v.f for each vertex v
2. as each vertex is finished, insert it onto the front of a linked list
3. 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 d, 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.

Answer 1

A topological ordering of a DAG $G$ is any ordering $v_1,\ldots,v_n$ of the vertices in which $(v_i,v_j) \in G$ implies $v_i \leq v_j$. That is, if there is an edge from $x$ to $y$, then $x$ must precede $y$ in the ordering (assuming $x \neq y$). A DAG can have many topological orderings. For example, the empty DAG on $n$ vertices has $n!$ topological orderings. In contrast, a path $v_1 \to v_2 \to \cdots \to v_n$ has a unique topological ordering.