Algorithms: Difference of output tree as subgraph from DFS and BFS

Question

I am an undergrad reading Cormen Intro. to Algorithms 3rd Ed and preparing for finals.

In Chapter 22 (page 603), it talks about how DFS produces a predecessor subgraph as a forest and how BFS produces a predecessor subgraph as a tree. I just don't understand.

My thought:

If vertex v is reachable from a source vertex s, on which one starts the search, would not the vertex v have some predecessor (may be distinct, but exist) regardless of DFS or BFS is run on the input graph? That is, it will be reachable by both DFS and BFS.

If so, how come DFS can produce a forest out of it, while BFS produce only one tree?

Thanks in advance!

Answer 1

Check the underline note on page 603, which begins with "It may seem arbitrary that breadth-first search is limited to only one source whereas depth-first search may search from multiple sources ..."

The number of sources is the reason one is a tree (single root/source) and the other is a forest (multiple roots/sources).

PS. This is, of course, not some conceptual difference, but merely a choice made by the authors, for reasons explained in the underline note.