1
$\begingroup$

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: directed graph example

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.

$\endgroup$
  • $\begingroup$ If those were to indicate valid orders of events, it means you don't have complete information about the order of the events. That's actually quite common in distributed systems that don't assume all agents have precisely synchronized clocks and are honest when reporting the time. $\endgroup$ – Jeffrey Bosboom Jun 3 '18 at 20:39
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.