Consider a directed graph $G=\{V,E\}$ with vertex set V = {A, B, C, D} and edge set E = {AB, AC, BC, BD, DC}. Which of the following is a valid topological ordering of graph G?

Question

Accepted Answer

The correct option is (4):
A topological ordering of a directed graph is a linear arrangement of its vertices such that for every directed edge $(u, v)$, vertex $u$ must appear before vertex $v$ in the sequence. This property ensures that all precedence constraints are respected, which is critical for scheduling tasks or processing dependencies. The given graph has five precedence constraints defined by its edges $E = {AB, AC, BC, BD, DC}$: $A$ must precede $B$, $A$ must precede $C$, $B$ must precede $C$, $B$ must precede $D$, and $D$ must precede $C$. Let us test the sequence ABDC against all these dependencies. In this order, $A$ (1st) precedes $B$ (2nd), $C$ (4th), and $D$ (3rd). $B$ (2nd) precedes $C$ (4th) and $D$ (3rd). Crucially, $D$ (3rd) precedes $C$ (4th). Since every single directed edge constraint is fully satisfied, ABDC is confirmed as a valid topological ordering.

The incorrect option is (1):
The ordering ABCD is incorrect because it fails to satisfy one of the critical precedence constraints: $D \rightarrow C$. The edge $D \rightarrow C$ dictates that vertex $D$ must appear *before* vertex $C$ in any valid topological ordering. However, in the sequence A-B-C-D, $C$ is placed in the third position while $D$ is in the fourth position. This places $C$ before $D$, which is the reverse of the required dependency. Therefore, this sequence is not a valid topological sort.

The incorrect option is (2):
The ordering BACD is incorrect because it violates the fundamental precedence constraint $A \rightarrow B$. The presence of this edge requires that vertex $A$ must be scheduled *before* vertex $B$. In the sequence B-A-C-D, $B$ is listed first and $A$ is second, which directly contradicts the required dependency. Furthermore, $A$ and $B$ are the only vertices with an out-degree, and $A$ has no in-degree, meaning it must appear first. Since $B$ has an incoming edge from $A$, $B$ cannot be the starting vertex of the sort.

The incorrect option is (3):
The ordering BADC is incorrect for the same primary reason as option (2): it violates the precedence constraint $A \rightarrow B$. The edge $A \rightarrow B$ means that vertex $A$ must precede vertex $B$ in the linear arrangement. In the sequence B-A-D-C, $B$ is placed in the initial position and $A$ is placed second, which is a violation of the dependency rule. Moreover, this sequence also incorrectly places $C$ after $D$, which is correct for $D \rightarrow C$, but the earlier violation is sufficient to disqualify it.