GATE CS 2024 Set 1 Q35 — Graph Traversals (BFS, DFS)

For any breadth first search (BFS) tree $T$ rooted at $v$, every directed edge $(u, w)$ in the graph $G$ must satisfy the BFS level property:

Let us analyze the options with respect to this property:

• Forward edges (Option C): A forward edge $(u, w)$ goes from an ancestor $u$ to a descendant $w$ that is not a direct child. This implies: $$\text{level}(w) \ge \text{level}(u) + 2$$ Since this directly violates the BFS property $\text{level}(w) \le \text{level}(u) + 1$, no forward edges can exist in $G$ with respect to $T$. Thus, Option C is always true.
• Back edges (Option A): A back edge $(u, w)$ goes from a descendant $u$ to an ancestor $w$, so $\text{level}(w) < \text{level}(u)$, which satisfies the BFS property. For example, in $G$ with edges $\{(v, u), (u, v)\}$, the tree $T = \{(v, u)\}$ is both a DFS and BFS tree, and $(u, v)$ is a valid back edge.
• Cross edges (Option B): A cross edge $(u, w)$ connects nodes where neither is an ancestor of the other. For example, in $G$ with edges $\{(v, a), (v, b), (b, a)\}$, if DFS visits $a$ first and then $b$, the tree $T = \{(v, a), (v, b)\}$ is both a DFS and BFS tree, and $(b, a)$ is a valid cross edge.