Which of the following statements regarding Breadth First Search (BFS) and…

Final answer: The true statements are the following three statements (restated):

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

  Reason: In an undirected graph, a non-tree edge encountered during DFS always connects a node to an ancestor in the DFS tree, so it is classified as a back edge (hence it fits the forward/back description). Forward and cross edges do not arise in undirected DFS.

• 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.

  Reason: BFS explores vertices in increasing distance from the source. The edge (u,v) gives an alternative path to v of length dist(s,u)+1 (and vice versa), so |dist(s,u) - dist(s,v)| ≤ 1.

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

  Reason: Starting a BFS or DFS from any vertex visits its entire connected component. Repeating the search from any still-unvisited vertex enumerates all components.

Explanation for the incorrect statement (that a DFS tree is a shortest-path tree):

Counterexample: Take vertices s, v, w with edges (s,v), (v,w), and (s,w). A DFS starting at s that visits v first will then visit w via v, producing a tree path to w of length 2, even though the direct edge (s,w) gives distance 1. Thus a DFS tree need not be a shortest-path tree; BFS is the algorithm that produces shortest-path trees in unweighted graphs.

Conclusion: The correct statements are the three described above (every non-tree edge in DFS is a forward/back edge; BFS non-tree edges connect vertices whose distances differ by at most 1; and both searches can find connected components).