Spanning Tree VS. Spanning Forest

Question

What's the difference between a Spanning Tree and a Spanning Forest in graphs, conceptually.

Also, is it possible to construct a Spanning Forest through DFS or BFS traversals? Why? How?

I understand the Spanning Tree, but I couldn't find any clear explanations about spanning forests. Even Wikipedia (https://en.wikipedia.org/wiki/Spanning_tree), doesn't give a clear definition about it. My book (Data Structures & Algorithms, Wiley - sixth edition) also has no definition for spanning forests.

I was wondering, if we have a graph with for example three connected components in it, is it possible to construct a spanning forest by DFS/BFS traversals?

Answer 1

When there is only one connected component in your graph, the spanning tree = spanning forest.

But when there are multiple connected components in your graph. For example in following picture we have 3 connected components.:

So for each component, we will have a spanning tree, and all 3 spanning trees will constitute spanning forest

I was wondering, if we have a graph with for example three connected components in it, is it possible to construct a spanning forest by DFS/BFS traversals?

Yes it is possible. When there is only 1 connected component, your BFS or DFS will terminate visiting all the vertices and you will have a spanning tree (which in this case is equal to spanning forest).

But when you have more than 1 connected component, like in the picture, the only thing you have to do is start another BFS or DFS from an unvisited vertex. Your algorithm terminates when there is no unvisited vertex left and each BFS or DFS traversal will yield a spanning tree.