# Valid orderings for topological sort

I am reading Algorithms by Dasgupta et al and the graph section provides an example graph and mentions that there are 4 orderings with one of them being B, A, D, C, E, F.

Are the other 3?

• B, A, D, C, F, E
• B, D, A, C, E, F
• B, D, A, C, F, E

A source is a vertex with in-degree zero.

An order of the vertices is a topological order if deleting the vertices in that order deletes only sources.

Hence, you can verify that an order is topological by deleting one and one vertex, and never deleting a vertex with an in-edge.

Your answer is correct, the topological orders are B,{A,D},C,{E,F}, where you can choose the order inside the braces, i.e., there are four of them.

You can answer your own question by checking whether, for each edge $$(u,v)$$ of the graph, $$u$$ appears before $$v$$ in each of the three candidate topological orders that you listed.

• What do you mean by candidate topological order? – heretoinfinity Feb 1 at 13:03
• I mean that you can check each of the 3 additional topological orders that you listed to see if its actually a valid topological order. – Steven Feb 1 at 13:26
• I don't get your answer in your post (not comment). Regarding the comment, I have done checking and I am uncertain and would like to clarify before I misunderstand the rest of the chapter. I am new to this. – heretoinfinity Feb 1 at 14:01
• You are uncertain on the truth value of the statement "for each edge $(u,v)$ in the graph, $u$ appears before $v$ in all the orders given in the question" ? – Steven Feb 1 at 16:08
• Yes, I am uncertain – heretoinfinity Feb 1 at 17:55