GATE CSE 2025 Set 2 Q29

Question

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?
A) A DFS tree of G is a Shortest Path tree of G.
B) Every non-tree edge of G with respect to a DFS tree is a forward/back edge.
C) If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within 1 of each other.
D) Both BFS and DFS can be used to find the connected components of G.

Accepted Answer

Official answer: B) Every non-tree edge of G with respect to a DFS tree is a forward/back edge.; C) If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within 1 of each other.; D) Both BFS and DFS can be used to find the connected components of G.. Explanation: Let us analyze each statement for an undirected simple graph G: - Statement (A) is FALSE: A DFS tree does not guarantee shortest paths from the source. In an unweighted undirected graph, a BFS tree produces the shortest path tree, whereas DFS traverses deeply along one branch and may find significantly longer paths. - Statement (B) is TRUE: In the DFS traversal of an undirected graph, every edge of G is either a tree edge or a back edge (an edge connecting a vertex to its ancestor/descendant in the DFS tree). There are no cross edges between unrelated subtrees. - Statement (C) is TRUE: In an undirected BFS tree rooted at s, any non-tree edge (u, v) can only connect vertices at the same level or at adjacent levels. Therefore, |d(s, u) - d(s, v)| 1, meaning the distances are within 1 of each other. - Statement (D) is TRUE: Both BFS and DFS can traverse all reachable vertices from a given starting vertex. By repeatedly initiating BFS or DFS from an unvisited vertex until all vertices are visited, one can identify all connected components of G. Hence, statements B, C, and D are correct.

Answer

A) A DFS tree of G is a Shortest Path tree of G.

Answer

B) Every non-tree edge of G with respect to a DFS tree is a forward/back edge.

Answer

C) If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within 1 of each other.

Answer

D) Both BFS and DFS can be used to find the connected components of G.

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2025 Set 2

More on Graph Traversals

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2025 Set 2

More on Graph Traversals

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph GGG is/are TRUE?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2025 Set 2

More on Graph Traversals

Share this solution

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph GGG is/are TRUE?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2025 Set 2

More on Graph Traversals

Share this solution

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?