Breadth-first forest

Question

I was reading CLRS about BFS and DFS, and the algorithms presented therein, which I take to be somewhat standard, constructs a forest in DFS that includes all the nodes, whereas BFS only constructs a tree from a chosen node $s$, and leaves out all the other nodes that are not reachable from $s$.

It seems the BFS can be adapted to construct other trees to include non-reachable nodes from $s$ and form a "BFS forest", analogous to operation of the DFS. What is the reason for constructing a forest in DFS, but only a tree (that excludes unreachable nodes) in BFS?

Answer 1

This asymmetry reflects a "philosophical" difference between the two algorithms. Let us think for a moment about what each of them is trying to achieve.

DFS investigates properties related to the structure of the graph as a whole: a few examples among the many are finding strongly connected components, topological sorting, finding cycles, testing biconnectivity, testing planarity. In all those cases the output forest has a very direct and concrete meaning. For example, the usual classification of the edges as tree, forward, back or cross tells us something about what these edges "do" in the graph we are exploring.

On the other hand, BFS is normally used to determine distances w.r.t. a pre-selected node; even applications that do not explicitly mention such distances, such as testing bipartiteness, are somewhat related to the general idea of counting the steps taken in a path.

However, distances from different sources behave somewhat inconsistently: reachability sets of different nodes may be intersecting, and distances from the two original roots could be drastically different. Furthermore, when running DFS we don't care where we started searching -- as emphasized by the fact that DFS takes no input other than the graph itself -- but the output of a BFS is a function of its starting node: what would a BFS forest even mean?

Perhaps you might be able to build a structure along the lines of a depth first forest considering the minimum pairwise distances between all nodes, but it would be something very different and you wouldn't be able to get that kind of information from a single breadth first search, anyway.