GATE CS 2024 Set 1 — Question 45
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MSQ+2 / -0HardDFS Edge ClassificationGraph AlgorithmsAlgorithmsBFS TraversalGraphs (Data Structure)Programming & Data Structures
Algorithms → Graph Algorithms → BFS Traversal
Last updated
Question
Let be a directed graph and a depth first search (DFS) spanning tree in that is rooted at a vertex . Suppose is also a breadth first search (BFS) tree in , rooted at . Which of the following statements is/are TRUE for every such graph and tree ?
Correct answer
(C) There are no forward-edges in G with respect to the tree T
Solution
Let be a spanning tree of rooted at . We are given that is both a DFS tree and a BFS tree.Analysis of Edge Types:
1.Forward Edges: A forward edge in a DFS tree connects a node to a descendant that is not its child. This implies that the path from to in the tree has length . Thus, in the tree , the level of is at least .
However, is also a BFS tree. A fundamental property of BFS is that for any edge in the graph , the level difference satisfies . If there were a forward edge in , it would require . This contradicts the tree structure requirement that . Therefore, no forward edges can exist.2.Back Edges: A back edge connects a node to an ancestor. For example, a simple cycle yields a tree which is both DFS and BFS, with being a back edge. Thus, statement (A) is false.
3.Cross Edges: A cross edge connects two nodes where neither is an ancestor of the other. Consider with edges . If we visit 3 then 2 in DFS, the tree is edges . The edge is a cross edge (from 2 to the already visited 3). This same tree is a valid BFS tree (levels: 1 at 0; 2, 3 at 1). Thus, statement (B) is false.
4.Only Tree Edges: Since back and cross edges can exist, statement (D) is false.
Conclusion: Only statement (C) is always true.Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Graph Algorithms
2026 Set 2 Q12The set T represents various traversals over binary tree. The set S represents the order of…2026 Set 1 Q17Consider the following recurrence relations: For all ,…2026 Set 2 Q19Consider the following three ANSI-C programs, P1, P2, and P3. P1 [code] P2 [code] **P3**…2026 Set 1 Q23Let be an odd number greater than 100. Consider a binary minheap with elements stored in an…2026 Set 2 Q24Consider the following functions, where is a positive integer.…