Merging a forest of isolated vertices
The algorithm starts with no selected edges, treating each vertex as a separate tree. It checks edges in increasing weight order, skipping one whose endpoints are already connected and accepting one that joins different components.
For a connected graph, V−1 accepted edges form a spanning tree. Choices need not all touch one growing origin: several regions can grow before merging, unlike Prim’s single-tree organization.
References: [1]
Using union–find to detect cycles
Union–find records the identity of each current component. Equal endpoint representatives reveal an existing selected path and hence a cycle if the edge were added; different representatives are merged after acceptance. This avoids rescanning the selected graph for every edge.
Optimality depends on weight order as well as cycle avoidance. The light edge joining suitable components is a safe cut choice. Arbitrarily collecting acyclic edges can produce a spanning tree without minimizing its weight.
Ordering costs and disconnected graphs
On connected input, sorting E edges and processing them with efficient union–find gives a standard O(E log E) worst-case bound, with storage for edges and component state. Already ordered input can change the sorting work, so implementation and representation matter. General disconnected inputs additionally require initializing or visiting all V vertices; many isolated vertices therefore contribute time and storage beyond the edge term.
Negative and tied weights are allowed; ties can yield different equally optimal trees. A disconnected input produces a minimum spanning forest rather than one connected tree covering the entire graph.