Let G be a directed graph and T a DFS spanning tree in G rooted at vertex v. Suppose T is also a BFS

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2024 GATE-CS Algorithm paper.

Q: How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2024 question covers Graph Traversals (BFS and DFS) topic.

Q: What is the difficulty level of this question?

This GATE-CS 2024 Algorithm question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Let G be a directed graph and T a DFS spanning tree in G rooted at vertex v. Suppose T is also a 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 T.(B) There are no cross-edges in G with respect to T.(C) There are no forward-edges in G with respect to T.(D) The only edges in G are the edges in T.

Accepted Answer

Correct Answer: (C) onlyConcept -- DFS and BFS Tree Properties in Directed Graphs (from Cormen et al., CLRS):In a DFS tree on a directed graph, edges are classified as: Tree edges, Back edges (to ancestors), Forward edges (to descendants not via tree), Cross edges (to neither ancestor nor descendant).In a BFS tree, every edge (u,v) in the original graph satisfies d(v) <= d(u) + 1 where d denotes BFS distance from root. This means BFS distances differ by at most 1 for graph edges.Key property: If T is both a DFS tree and a BFS tree from v:(A) FALSE: Back edges can still exist (a back edge (u, ancestor) is possible in a DFS tree that is also a BFS tree if the ancestor is one level up).(B) FALSE: Cross edges can exist. A cross edge (u, w) where w is at the same or earlier BFS level is still permitted.(C) TRUE: Forward edges cannot exist. A forward edge (u, w) in DFS means w is a descendant of u but not a tree edge. In BFS terms, w would have d(w) < d(u), contradicting that u was discovered before w in DFS (since in DFS, u is an ancestor of w, so d_BFS(u) < d_BFS(w) in the BFS tree). When T is simultaneously a DFS and BFS tree, the DFS order and BFS distance ordering are consistent, and forward edges (which would go to deeper descendants via non-tree paths) cannot occur because they would require visiting a node at a greater BFS depth before its tree children, which contradicts the BFS property.(D) FALSE: G may have additional edges (back edges, cross edges) beyond the tree edges.

Master GATE-CS with Our Test Series

More Questions from Graph Traversals (BFS and DFS)

Frequently Asked Questions

Master GATE-CS with Our Test Series

More Questions from Graph Traversals (BFS and DFS)

Frequently Asked Questions