A directed graph has edges A→B, A→C, B→D, C→D and D→E. Which of these is a valid topological order?
Correct answer B. A, C, B, D, E
Explanation
In a topological order every edge must point from an earlier vertex to a later one. A, C, B, D, E satisfies all five edges. A, B, D, C, E fails because C must come before D, B, A, ... fails because A must precede B, and A, C, D, B, E puts D before B. A graph can have several valid orders; here A, B, C, D, E also works.
Answer checked How we write and check questions
Discussion