GATE CS 2007 Q5 — Graph Traversals (BFS, DFS)

In the given Directed Acyclic Graph (DAG), the directed edges are:

• $1 \to 2$ and $1 \to 3$
• $2 \to 4$ and $3 \to 4$
• $4 \to 5$ and $4 \to 6$

A topological ordering of a DAG is a linear ordering of its vertices such that for every directed edge $u \to v$, vertex $u$ comes before $v$ in the ordering.

From the edge constraints:

• Since there are directed edges $1 \to 2$ and $1 \to 3$, vertex $1$ must appear before both $2$ and $3$.
• Since there are directed edges $2 \to 4$ and $3 \to 4$, both $2$ and $3$ must appear before $4$.

Looking at Option D: 3 2 4 1 6 5

Here, vertex $1$ appears after $2$, $3$, and $4$. This violates the dependency constraints $1 \to 2$ and $1 \to 3$. Therefore, this is not a valid topological ordering.