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?

Hordein

It's quite simple, each connected component of your graph generates a spanning tree, all of which together are called a spanning forest. – Tomasz

@Rishav Thanks for reply. Could you explain it on this picture fro example? en.wikipedia.org/wiki/Connected_component_(graph_theory)#/media/… – Hordein

I don't have a photo editor at the moment, but are you familiar with the concept of connected components? A connected component consists of all those vertices which are reachable from each other. There are 3 of those in that picture. Each of these components are used to generate a single spanning tree. When you take the set of all 3 of those spanning trees, it's called a spanning forest. – Tomasz

@NimaSalami Feel free for any queries. – Belligerent

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.

Belligerent

At least according to the current version of Wikipedia, this definition of spanning forest is uncommon. The Wikipedia article states that your definition of "a forest of spanning trees" is sometimes called a "full spanning forest". The typical definition, however, is apparently that given any undirected graph G, any subgraph H is a spanning forest of G as long as H has the same set of vertices as G, with no further requirements on which edges it should include. – Contrail

Answer 2

Non-trivial spanning forests can be constructed even for complete graphs via the following algorithm:

preconditions

• all vertices are unmarked
• the edges are enumerated from 1 to m

edge processing

• if both of its adjacent vertices are marked, skip it because then that edge would either merge trees of the forest or creates a cycle in one of its trees
• else mark its unmarked adjacent vertices

algorithm
process the edges in the order of their enumeration

explanaton:
while it is feasible in the construction of spanning trees to add edges that "bridge" connected components, those edges are not added in the above algorithm.

interpretation:
if the edges are enumerated according to ascending length, the edges of the resulting spanning forest will be a subsets of the MST and the trees of the forest will resemble "basins" i.e. the length of edges is smallest for the one that created the connected component and increases with every edge that is attached in later steps.
In that case the properties of spanning forest may provide insight into the structural properties of the original graph and/or be utilized in algorithms.

Jaan