GATE CS 2014 Set 1 Q13 — Graph Traversals (BFS, DFS)

The given directed graph has the following vertices and directed edges:

• Vertices: $P, Q, R, S$
• Edges: $P \to R$, $P \to Q$, $S \to R$, $S \to Q$, and $R \to Q$

We can determine the topological orderings by analyzing the in-degrees of the vertices:

• $\text{in-degree}(P) = 0$
• $\text{in-degree}(S) = 0$
• $\text{in-degree}(R) = 2$ (incoming from $P$ and $S$)
• $\text{in-degree}(Q) = 3$ (incoming from $P$, $S$, and $R$)

Since a topological sort must begin with a vertex of in-degree $0$, we have two possible starting choices:

1. Start with $P$: After removing $P$, the vertex $S$ is the only remaining vertex with an in-degree of $0$. Removing $S$ leaves $R$ with an in-degree of $0$, and finally $Q$ is left. This gives the sequence PSRQ.
2. Start with $S$: After removing $S$, the vertex $P$ is the only remaining vertex with an in-degree of $0$. Removing $P$ leaves $R$ with an in-degree of $0$, and finally $Q$ is left. This gives the sequence SPRQ.

Thus, both PSRQ and SPRQ are valid topological orderings.