Spanning Tree VS. Spanning Forest
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
.