DAG is given, which of the following is NOT a topological order?

2022

DAG is given, which of the following is NOT a topological order?

  1. A.

    ABCDEF

  2. B.

    ACBDEF

  3. C.

    ACBDFE

  4. D.

    CBDAFE

Attempted by 132 students.

Show answer & explanation

Correct answer: D

Option (d) starts with C, B, D… But A must come before both B and C, because A → B and A → C are edges. Since A appears later in the order, this violates topological ordering, so (d) is NOT a valid order.

Explore the full course: Niacl Ao It Specialist