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

---

Please share the link with time stamp. I think he not solve this question, i checked. Please provide link if you have.

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

First of all it is connected graph...and not mention to take strongly connected in question.

If graph not strongly connected with E than how DFS can even visit.

Counter example is front of u where dfs and bfs same but cross edge there

---

You are wrong about bfs...It also start from E

---

@minip Correct answer will be C only and not B & C. 
The BFS & DFS will produce the same tree and cross edge exists from 3 to 2 

---

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