Minimum spanning forest

A forest containing one minimum spanning tree of each connected component of a graph of a finite undirected weighted graph, including isolated vertices. For disconnected input, Kruskal's algorithm returns a minimum spanning forest.

Among all acyclic graphs contained in a finite weighted undirected graph, with no requirement to connect vertices, one optimum is obtained by keeping only strictly negative edges and computing their minimum spanning forest. Removing a nonnegative edge never worsens weight or creates a cycle. Within a connected component of the negative-edge subgraph, any disconnected candidate forest can be extended by a negative crossing edge, strictly improving its weight. Hence an optimum must span each such component and minimise its tree weight. Kruskal's algorithm on the negative edges therefore solves the problem. Zero-weight edges are optional when they preserve acyclicity.