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!

If BFS will produce a tree - so will DFS.

amit
– amit

2013-12-15 08:02:29 +00:00
Commented Dec 15, 2013 at 8:02 — amit
– amit, Commented Dec 15, 2013 at 8:02

chill · Accepted Answer · 2013-12-15 09:32:13Z

3

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.

answered Dec 15, 2013 at 9:32

chill

17k2 gold badges42 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related