UGC NET CSE | December 2005 | Part 2 | Question: 23

Question

Consider the graph, which of the following is a valid topological sorting?

• A. $\text{ABCD}$
• B. $\text{BACD}$
• C. $\text{BADC}$
• D. $\text{ABDC}$

Comments

Topological Sort is a linear ordering of the vertices in such a way that

if there is an edge in the DAG going from vertex ‘u’ to vertex ‘v’, then ‘u’ comes before ‘v’ in the ordering.

according to this option d is correct

Answer 1

Option A:  incorrect as  $C$ cannot be completed before  $D$

Option B:  incorrect as  $B$ cannot be completed before  $A$

Option C:  incorrect, same reason as that for Option B

Option D: correct answer. Topologically sorted order would be:  $A\rightarrow B\rightarrow D\rightarrow C$