What is a minimum spanning forest?

algorithm graph graph-theory minimum-spanning-tree
Nikunj Banka picture Nikunj Banka · Jan 13, 2013 · Viewed 10.3k times · Source

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?

Answer

voidengine picture voidengine · Jan 13, 2013

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.

Related questions

Cycles in an Undirected Graph

Given an undirected graph G=(V, E) with n vertices (|V| = n), how do you find if it contains a cycle in O(n)?

Read More
Difference between hamiltonian path and euler path

Can some one tell me the difference between hamiltonian path and euler path. They seem similar!

Read More
How to remove cycles in an unweighted directed graph, such that the number of edges is maximised?

Let G be an unweighted directed graph containing cycles. I'm looking for an algorithm which finds/creates all acyclic graphs G', composed of all vertices in G and a subset of edges of G, just small enough to make G' …

Read More