Search code examples
directed-acyclic-graphstopological-sort

Topological sort orderings on a disconnected DAG


If the numbers 0,1,2 are nodes in a directed acyclic graph and we have only 1 edge: 1 -> 2. Then all valid orderings are:

 1,2,0
 0,1,2
 1,0,2

Am I correct? I'm only not sure about the last ordering: 1,0,2 Is it valid?


Solution

  • Yes you are correct.

    According to the definition, the only condition for topological ordering is that for every directed edge u->v u should come before v. It is not said that it should come just before v.

    Consider the vertices to represent tasks to be performed, say you getting ready. Say 0 is putting on a tie, 1 is wearing a pair of socks and 2 is wearing shoes. Thus 1 comes before 2(1->2). As you can see, the last ordering you have written, can be considered to be a topological order(Wear socks, then tie and then your shoes)