What is a minimum spanning forest?

Question

A minimum spanning tree gives the cheapest way an undirected graph. But what is a minimum spanning forest? Is it defined for connected graphs or unconnected graphs?

Solution

Minimum spanning forest is a generalization of minimum spanning tree for unconnected graphs. For every component of the graph, take its MST and the resulting collection is a minimum spanning forest.

Comments

[Labo]

Excuse me, but I am not sure about what you are saying. If you have a minimum spanning forest, aka a subset of the vertices such that every vertex has at least an adjacent edge in the forest, then it will almost never match your definition which leads to a far bigger forest.

[voidengine]

@Labo are you saying that forest is a subset of vertices? That just doesn't make sense

[Labo]

A minimal subset of vertices IS a forest, since it is a graph without cycle. I am not saying your definition is false, just that it could be defined in an other way.

[voidengine]

That would be a forest, but by no means a spanning one. Where there's a path in the (disconnected) graph, there must be one in the spanning forest as well. The wording of the definition may of course differ, but the essence won't.

[Alan Evangelista]

From the definition, I assume that the minimum spanning forest does not contain the isolated vertices of the graph, which are not connected to any other vertices?