Consider the following DAG (Directed Acyclic Graph): Which of the
Consider the following DAG (Directed Acyclic Graph):
Which of the following is/are can be the linear order of Topological sort?
i) A, B, C, D, E, F
ii) F, A, B, C, E, D
iii) F, A, B, C, D, E
- A.
Only i
- B.
Only i, ii
- C.
Only ii, iii
- D.
Only i, iii
Attempted by 93 students.
Show answer & explanation
Correct answer: D
Topological sort is the linear ordering of nodes of a directed graph so that the directed edges go only from left to right. In both I and iii, all the directed edges go from left to right only. In ii, the edge from D to E cannot go from left to right.