Consider a directed graph G = (V, E), a source vertex s ∈ V, and a tree edge set Eₜ ⊆ E such that for every vertex v ∈ V, the unique simple path from s to v in (V, Eₜ) is a shortest path in G.
Which of the following statements is TRUE?
A) Such a tree Eₜ must always be generated by running BFS from s on G, with appropriate vertex ordering in adjacency lists.
B) Such a tree Eₜ can never be generated by BFS, because BFS does not compute shortest paths.
C) There exists a graph G and a shortest-path tree Eₜ such that Eₜ cannot be produced by any BFS traversal of G, no matter how adjacency lists are ordered.
D) Every shortest-path tree in G must correspond to some BFS tree from s, since BFS always finds all shortest paths.
