Spanning Tree VS. Spanning Forest

algorithm graph-theory depth-first-search breadth-first-search spanning-tree
Nima Salami picture Nima Salami · Apr 6, 2017 · Viewed 8.3k times · Source

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

Sumeet picture Sumeet · Apr 6, 2017

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.:

enter image description here

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.

Related questions

When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?

I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other? Could anyone give any examples of how DFS would trump BFS and vice versa?

Read More
Why DFS and not BFS for finding cycle in graphs

Predominantly DFS is used to find a cycle in graphs and not BFS. Any reasons? Both can find if a node has already been visited while traversing the tree/graph.

Read More
What is breadth-first search useful for?

Usually when I've had to walk a graph, I've always used depth-first search because of the lower space complexity. I've honestly never seen a situation that calls for a breadth-first search, although my experience is pretty limited. When does it …

Read More