CODEWITHSUNDEEP
directed-acyclic-graphstopological-sort
user7841392
user7841392

Reputation:

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?

Upvotes: 1

Views: 2050

Answers (1)

maigar
maigar

Reputation: 197

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)

Upvotes: 2

Related Questions