GATE CSE 2024 | Set 1 | Question: 35

Question

​​​​Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth first search $\text{(BFS)}$ tree in $G$, rooted at $v$. Which of the following statements is/are TRUE for every such graph $G$ and tree $T$?

• A. There are no back-edges in $G$ with respect to the tree $T$
• B. There are no cross-edges in $G$ with respect to the tree $T$
• C. There are no forward-edge in $G$ with respect to the tree $T$
• D. The only edges in $G$ are the edges in $T$ 

Comments

@Sachin Mittal 1 plz verify this question, ans should be C only 

---

You can refer to Sachin Mittal's Youtube Video on Exam Day. I guess he told, all of the above options. Please recheck

Answer 1

1. Back edge possible

2. cross edge possible

3. all edge of G not in T

Forward edge cant be there else it wont give same BFS and DFS 

Ans must be option C which always true 

Comments

Nice counterexample!!

---

In this example, Vertex 'e' isn't reachable from 'a' in BFS but DFS will still cover it. So, we cannot take this as an counter-example.

To have BFS & DFS produce same tree, we must agree on that the input graph is connected. So, Taking your example without vertex 'e' we can see that back edges are still possible but forward and cross edges aren't possible.

Kindly correct me if incorrect

---

There is no directed edge or path to E so no one can cover E from A

Not mention strongly connected graph in question anywhere

---

Can you explain how DFS covers 'e' from 'a'?

Answer 2

Cross Edges can be present.

Comments

By following your way of traversal, the bfs and dfs tree won't be same. The question clearly says let "T" be "a" dfs spanning tree which is also a bfs spanning tree. Clearly, for the above graph same tree exists when (order of visiting vertices is as follows)
1) DFS -> 1->2->4 (backtrack) -> 5 (backtrack) -> 3
2) BFS -> 1->2->3->4->5
These are exactly same tree's and a cross edge(3->2) is present. Since the question asked "Which of the statements is/are true for "EVERY" such graph G and T.", 1 single counter example is sufficient to prove false. This eliminates option D and B. Option A is eliminated when there is a cycle, so clearly answer is only option C.

---

Now check ans given is C

---

rank predictor m to A,B,C use hora hai