Currently learning about topological sorting. My teacher gave us this problem.

enter image description here

The answer given to us is : B,A,C,E,D,G,F,H in lexicographical order.

Why does the order go from B,A,C THEN go to E and then D IF it is in lexicographical order? Also, can another topological sort of this graph be: B,A,C,D,E,G,F,H?

  • 1
    $\begingroup$ If the diagram had an edge from E to D, the teacher's answer would be correct but, otherwise, D should come before E if we want the lexicographically first solution. $\endgroup$ – David Richerby Dec 4 '14 at 17:15
  • $\begingroup$ Agree with David, teacher made a mistake. $\endgroup$ – Yuval Filmus Dec 4 '14 at 17:19

The comments are right. In a topological sort, we start with nodes that have no incoming arrows and remove them from the graph, so to speak. In this case, if there are multiple possible nodes to remove, then we want to remove them in lexicographical order. Hence, the order should be $B, A, C, D, E , F, G, H$.

Your suggest topological sort does not work. This is because you propose to put $G$ before $F$.


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.