Correct : d

The correct answer is Option D — Both BFS and DFS can be used to find the connected components of G.
Let''s evaluate each option for an undirected simple graph G.
Option A - A DFS tree is a shortest path tree: False. DFS dives deep without regard for edge count, so DFS tree paths are not necessarily shortest. It''s BFS that guarantees shortest paths in unweighted graphs.
Option B - Non-tree edges in DFS are forward/back edges: False as stated. In an undirected graph, all non-tree edges in a DFS are back edges only- there are no forward edges or cross edges. The option mentions "forward/back" which makes it incorrect since forward edges don''t appear in undirected DFS.
Option C - Non-tree BFS edge (u,v): distances within ±1: This is actually true for undirected graphs - if (u,v) is a non-tree edge in a BFS tree, then |d(u) − d(v)| ≤ 1. However, the official GATE key marks only D as correct, possibly because the question intends a stricter interpretation or the phrasing implies something broader.
Option D - Both BFS and DFS find connected components: True. Running BFS or DFS from each unvisited vertex and grouping all visited vertices together gives the connected components. Both algorithms explore all reachable vertices from a source, making them equally capable of connected component detection.