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

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)| \le 1$, meaning the distances are within $\pm 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.