# Questions on Topological Sorting

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

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?

• 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. – David Richerby Dec 4 '14 at 17:15
• Agree with David, teacher made a mistake. – 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$.