Search code examples
algorithmgraphminimum-spanning-treeminimum-spanning-forest

What algorithms are used to find a minimum spanning forest?


As Wikipedia says:

Minimum spanning forest is a union of the minimum spanning trees for its connected components.

For finding minimum spanning tree we can use for example Prim's algorithm, Kruskal's algorithm, or Borůvka's algorithm.

What algorithm can we use to find minimum spanning forest?


Solution

  • I don't see how you need any other algorithm than you use for trees - you may need to adapt them a bit.
    If you use for example Kruskal's algorithm you get all cheapest edges in every sub graph/minimum spanning tree of your (now also minimum spanning) forest. Or you can use Prim's algorithm and if your iteration stops, restart it with a node that is not connected yet (i.e. with another tree).

    So my answer in one sentence: "The algorithms used to find a minimum spanning forest are the same ones that are used to find a minimum spanning tree - in some cases with adaptions and in some cases without them."