4 votes 4 votes 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$?There are no back-edges in $G$ with respect to the tree $T$There are no cross-edges in $G$ with respect to the tree $T$There are no forward-edge in $G$ with respect to the tree $T$The only edges in $G$ are the edges in $T$ Algorithms gatecse2024-set1 algorithms multiple-selects graph-search + – Arjun asked Feb 16 • retagged Apr 26 by Arjun Arjun 3.6k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Manoj5130 commented Feb 17 reply Follow Share @Sachin Mittal 1 plz verify this question, ans should be C only 1 votes 1 votes minip commented Feb 17 reply Follow Share You can refer to Sachin Mittal's Youtube Video on Exam Day. I guess he told, all of the above options. Please recheck 0 votes 0 votes Vijay Devagonda commented Apr 11 reply Follow Share Please share the link with time stamp. I think he not solve this question, i checked. Please provide link if you have. 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes 1. Back edge possible2. cross edge possible3. all edge of G not in TForward edge cant be there else it wont give same BFS and DFS Ans must be option C which always true Manoj5130 answered Feb 17 Manoj5130 comment Share Follow See all 4 Comments See all 4 4 Comments reply ProFFeSoR commented Feb 17 reply Follow Share Nice counterexample!! 1 votes 1 votes minip commented Feb 17 reply Follow Share 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 0 votes 0 votes Manoj5130 commented Feb 17 i edited by Manoj5130 Feb 17 reply Follow Share 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 1 votes 1 votes ProFFeSoR commented Feb 17 reply Follow Share Can you explain how DFS covers 'e' from 'a'? 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes Cross Edges can be present. minip answered Feb 17 • edited Feb 18 by minip minip comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments ProFFeSoR commented Feb 17 reply Follow Share 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) -> 32) BFS -> 1->2->3->4->5These 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. 2 votes 2 votes Manoj5130 commented Feb 18 i edited by Manoj5130 Feb 18 reply Follow Share Now check ans given is C 1 votes 1 votes Philosophical_Virus commented Feb 18 reply Follow Share rank predictor m to A,B,C use hora hai 0 votes 0 votes Please log in or register to add a comment.