Search code examples
algorithmgraphgraph-theoryminimum-spanning-tree

What is a minimum spanning forest?


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.